LeetCode - 28 Days Leeter Part 1

function findPivotIndex(nums):
    // iterate through the array
    for i from 0 to length of nums - 1:
    leftSum = 0
    rightSum = 0
    
      // calculate the sum of the elements to the left of index i
      for j from 0 to i - 1: 
        leftSum += nums[j]
      
      // iterate through the array adding 1 to i until rightSum is equal to left 
      for k from i + 1 to length of nums - 1:
        rightSum += nums[k]

     leftSum === rightSum: return i

    return -1 // Return -1 no pivot index is found

const nums: number[] = [1, 7, 3, 6, 5, 6]

console.log(findPivotIndex(nums)) // OUTPUT index: 3

const pivotIndex = (nums: number[]): number => {
  // Calculate the total sum of the array in one pass 
  // removes the need for a first loop in the brute 
  const totalSum: number = nums.reduce((accumulator, currentValue) => accumulator + currentValue)
  let leftSum: number = 0 // Initialize leftSum to 0
  let rightSum: number = 0 // Initialize rightSum to 0

  // iterate through the array
  for (let i = 0; i < nums.length; i++) {
    // for each index, the sum of elements to the right can be 
    // derived using the total sum and the left sum 
    // minus the current element 
    rightSum = totalSum - leftSum - nums[i]

   // Check left sum equals right sum
  (rightSum === leftSum) return i // Found the pivot index
        // keeping track of the sum of elements 
        // to the left of the current index
    leftSum += nums[i] // Update the left sum for the next iteration
  }

  return -1 // Return -1 no pivot index is found
}

// choose an array to test
const nums1: number[] = [1, 7, 3, 6, 5, 6] // 3
const nums2: number[] = [1, 2, 3] // -1 none
const nums3: number[] = [2, 1, -1] // 0

console.log('Pivot Point: ', pivotIndex(nums1)) // OUTPUT pivot point 3

function merge(nums1, m, nums2, n):

  for i form 0 to n - 1:
      nums1[m + i] = nums2[i]

  sort(nums1)

const nums1: number[] = [1, 2, 3, 0, 0, 0]
const m: number = 3
const nums2: number[] = [2, 5, 6]
const n: number = 3

merge(nums1, m, nums2, n)

console.log('merged nums2 into nums1 ', nums1) 
// OUTPUT: merged nums2 into nums1 Array(6) [ 1, 2, 2, 3, 5, 6 ]

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  // Start from the End: Using three pointers:
  /** to track the last element in `nums1` 
  (excluding the extra space) */
  let mIndex = m - 1 
  // to track the last element in `nums2`
  let nIndex = n - 1 
  /** get the last item in `nums1` 
  (`m:3 + n:3 = length - 1`) */
  let pointerEnd = m + n - 1 

  /** Merge nums1 and nums2 starting from the end
  While there are elements in nums2 to merge */
  while (nIndex >= 0) {
    /** Compare elements from nums1 and nums2 
    and place the larger one at the end */
   (mIndex >= 0 && nums1[mIndex] > nums2[nIndex]) {
      nums1[pointerEnd] = nums1[mIndex] // Place element from nums1 at end 
      mIndex-- // Move the pointer in nums1 to the left
    } else {
      nums1[pointerEnd] = nums2[nIndex] // Place element from nums2 at end 
      nIndex-- // Move the pointer in nums2 to the left
    }

    pointerEnd-- // Move the end pointer to the left
  }
}

// test solution
const nums1: number[] = [1, 2, 3, 0, 0, 0]
const m: number = 3
const nums2: number[] = [2, 5, 6]
const n: number = 3

merge(nums1, m, nums2, n)
console.log('merged nums2 into nums1: ', nums1) 
// OUTPUT merged nums1: Array(6) [ 1, 2, 2, 3, 5, 6 ]

function findMaxAvgBruteForce(nums, k):
  // initialize maxSum to the smallest possible value
  maxSum = -Infinity

  // Outer loop to iterate through each starting index of subarrays of length k ensuring all subarrrays are considered 
  for i from 0 to nums.length - k:
    // initialize a currentSum to compare with maxSum
    currentSum = 0

    // Calculate the sum of the subarray of length k starting at index i
    for j from i to i + k - 1:
      currentSum += nums[j]

    // Update maxSum if currentSum is
    if currentSum > maxSum:
      maxSum = currentSum

  // Calculate and return the maximum
  return maxSum / k

const nums[] = [1, 12, -5, -6, 50, 3]
const k: number = 4

console.log(findMaxAvgBruteForce(nums, k)) // 12.75

const findMaxAverage = (nums: number[], k: number): number => {
  let currentSum: number = 0
  
   // sum of the first k elements is calculated using a for loop initialize window
  for (let i = 0; i < k; i++) {
    currentSum += nums[i]
  }
  
  // Initialize maxSum with the sum of the first window
  let maxSum: number = currentSum

  // Slide the window from start to end of the array
  for (let i = k; i < nums.length; i++) {
    // Update the window sum by subtracting the element that goes out and adding the new element
    currentSum = currentSum - nums[i - k] + nums[i]
    // Update the maximum sum found so far 
    if (currentSum > maxSum) { 
      maxSum = currentSum;
    }
  }

  // Calculate and return the maximum average
  return maxSum / k
}

const nums: number[] = [1, 12, -5, -6, 50, 3]
const k: number = 4

console.log(findMaxAverage(nums, k)) // 12.75 or 12.750000

function hasCycleBruteForce(head):
  if head is null or head.next is null: 
    return false // Empty list or single node, no cycle

  // Create a set to store the visited nodes
  visitedNodes = new Set()

  // Initialize currentNode to the head of the list
  currentNode = head

  // Loop through the linked list 
  while currentNode is not null and currentNode.next is not null:
    // check if the current node is in the set 
    if visitedNodes has currentNode: 
      return true // Cycle detected
    
    // Insert a new element current node to the set
    add currentNode to visitedNodes

    // Move to the next node 
    currentNode = currentNode.next

  
  return false // no cycle detected

// Create nodes to test for cycle
const node1 = new ListNode(1)
const node2 = new ListNode(2)
const node3 = new ListNode(3)
const node4 = new ListNode(4)

// Link nodes: 1 -> 2 -> 3 -> 4
node1.next = node2
node2.next = node3
node3.next = node4

// Create a cycle: 4 -> 2
// node4.next = node2
// No cycle
node4.next = null
  
console.log('Has Cycle: ', hasCycleBruteForce(node1)) // OUTPUT false
console.log('Has Cycle: ', hasCycleBruteForce(node1)) // OUTPUT true

/**
 * Definition for singly-linked list.
 **/
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

const hasCycle = (head: ListNode | null): boolean => {
  if (head === null || head.next === null) return false

  let slowPointer: ListNode | null = head
  let fastPointer: ListNode | null = head

  // ensure both the fastPointer and its next element exist before attempting to access fastPointer.next.next
  while (fastPointer !== null && fastPointer.next !== null) {
    slowPointer = slowPointer.next
    fastPointer = fastPointer.next.next

    if (slowPointer === fastPointer) return true
  }

  return false
}

// Create nodes to test for cycle
const node1 = new ListNode(1)
const node2 = new ListNode(2)
const node3 = new ListNode(3)
const node4 = new ListNode(4)

// Link nodes: 1 -> 2 -> 3 -> 4
node1.next = node2
node2.next = node3
node3.next = node4

// Create a cycle: 4 -> 2
node4.next = node2

console.log(hasCycle(node1)) // OUTPUT true

function reverseListBruteForce(head):
    // Check for empty or single node list
    if head is null or head.next is null:
   //  If yes, return head as there is nothing to reverse
        return head

    // Initialize an empty array to store nodes
    nodes = []
    currentNode = head

    // Traverse the list and store each node in the array
    while currentNode is not null:
        add currentNode to nodes
        currentNode = currentNode.next

    // Reverse the list by updating next pointers
    for i from length of nodes - 1 to 1:
    // Set the next pointer of the current node to the previous node
        nodes[i].next = nodes[i - 1]

    // Handle the new tail
    nodes[0].next = null

    // Return the new head
    return nodes[length of nodes - 1]

/**
 * Definition for singly-linked list.
 **/
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

const reverseList = (head: ListNode | null): ListNode | null => {
  let prev: ListNode | null = null
  let curr: ListNode | null = head

  while (curr !== null) {
    const next: ListNode | null = curr.next // get the next node
    curr.next = prev // set the next to the previous node reverse
    prev = curr // move the node previous to current
    curr = next // move to the next node in line
  }

  return prev
}

// Create nodes to test
const node1 = new ListNode(1)
const node2 = new ListNode(2)
const node3 = new ListNode(3)
const node4 = new ListNode(4)
const node5 = new ListNode(5)

// Link nodes: 1 -> 2 -> 3 -> 4
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

console.log(reverseList(node1)) // 5, 4, 3, 2, 1

function levelOrder(root):
  // Check if the root is none (empty tree) 
  if root is null:
    return []
  
  // Initialize result list store the final level
  // order traversal
  result = []
  // Initialize the queue with the root node
  queue = [root] 
  
  // Traversal of queue until the queue empty 
  while queue is not empty:
    // Get the number of nodes at the current level
    levelSize = length of queue
    // List to store of nodes at the current level
    currentLevel = []

    // Process all nodes at the current level
    for i from 0 to levelSize - 1
      // Remove the first element from the queue
      node = queue.shift()
      // add the node value to the current level
      currentLevel.push(node.val)

      // If the left child exists 
      if node.left is not null:
       // add left node for the next level
        queue.push(node.left)
      // If the right child exists 
      if node.right is not null:
      // add right node
        queue.push(node.right)

    // Add the current level list to the 
    // result list
    result.push(currentLevel)
  
  // List levels containing the values of nodes in level order
  return result

/**
 * Definition for a binary tree node.
 * TreeNode Class: Defines the structure of a node in the binary tree, with a value and pointers to left and right children.
 *  */

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

const levelOrder = (root: TreeNode | null): number[][] => {
  // Initial Check: If the tree is empty, return empty list.
  if(root === null) return []
  // Initialize result list store the final level
  // order traversal
  const result: number[][] = []
  // Queue Initialization: Start with a queue containing the root node
  const queue: TreeNode[] = [root]
  // Simulate a dequeue by maintaining a head pointer
  let head: number = 0

  // Traverse queue until the all
  // nodes have been processed
  while (head < queue.length) {
    // Determine the number of nodes at the current level (levelSize).
    const levelSize: number = queue.length - head
    // Initialize an array to store the values of nodes at the current level
    const currentLevel: number[] = []

    // Use a loop to process all nodes at the current level
    for (let i = 0; i < levelSize; i++) {
      // Dequeue the current node
      let node: TreeNode = queue[head++]
      /** Add the current node value to the 
      level list */ 
      currentLevel.push(node.val)

      // Enqueue if left node exists
      if (node.left !== null) {
        queue.push(node.left)
      }

      // Enqueue if right node exists
      if (node.right !== null) {
        queue.push(node.right)
      }
    }

    /** Store Current Level: 
    After processing all nodes at 
    the current level, add the currentLevel 
    list to the result */
    result.push(currentLevel)
  }

  /** Return the result list contain
  the level order traversal */
  return result
}

// Input:
const root = new TreeNode(3)
root.left = new TreeNode(9)
root.right = new TreeNode(20)
root.right.left = new TreeNode(15)
root.right.right = new TreeNode(7)

console.log(levelOrder(root)) // Output: 0: Array [3] 1: Array [9,20] 2: Array [15,7] length: 3

function mergeIntervals(intervals):
  // Check if the intervals list is empty
  if(intervals.length === 0) 
    return []

  result = []

  // Sort intervals based on their start values 
  while intervals.length > 0:
    interval = intervals.pop()
    let merged = false

  // Loop thru the intervals in the result 
  for i from 1 to intervals.length - 1:
  // Check if the current interval overlaps with the interval in the result  
    if interval[0] <= result[i][1] && interval[i] >= result[i][0]):
     // Merge intevals by updating start and end 
      result[i][0] = min(result[i][0], interval[0])
      result[i][0] = max(result[i][1], interval[1])
      merged = true
      break 

      if not merged:
      // If no overlap, add the current interval to the result
      add interval to result

  return result

const merge = (intervals: number[][]): number[][] => {
  if (intervals.length === 0) return []
  // sort intervals
  intervals.sort((a, b) => a[0] - b[0])

  const result: number[][] = [intervals[0]]

  for (let i = 0; i < intervals.length; i++) {
    const current: number[] = intervals[i]
    const lastInterVal: number = result[result.length - 1]

    if (current[0] <= lastInterVal[1]) {
      lastInterVal[1] = Math.max(lastInterVal[1], current[1])
    } else {
      result.push(current)
    }
  }

  return result
}

const intervals: number[][] = [
  [1, 3],
  [15, 18],
  [8, 10],
  [2, 6],
]

console.log('merge if overlap: ', merge(intervals)) // [ 1, 6 ], [ 8, 10 ], [ 15, 18 ]