AlgoExpert Medium

Question 1

Three Number Sum

Answer 1

O(N^2) Time | O(N) Space

Pattern:

• Sort the array, so that you know which side to incre/decrement
• Loop through array:
  
  • Set left to i+1, right to last.
  • If equal, append result, and incre/decrement
  • If smaller increment left, if bigger decrement right

Question 2

Smallest Difference

Answer 2

O(n log n) time | O(1) space

Pattern:

• sort the two arrays, create two idx, smallestPair, smallestDifference, currDiff
• Loop while both idx is smaller than len
  
  • get both numbers
  • If one number is larger than the other, make it the currDiff, increment the idx for smaller number
  • Check if currDiff is smaller than smallest. If it is update smallest and smallest Pair
• Return smallest Pair

Question 3

Move Element To End

Answer 3

O(N) Time | O(1) Space

Pattern:

• Set two idx, one at start, one at end of array.
• Loop while left and right:
  
  • Loop while right == target and left < right
  • If left is toMove, swap it with right (since it is not target)
  • Increment left

Question 4

Monotonic Array

Answer 4

O(N) space | O(1) time

Pattern:

• If they fluctuate between increasing and decreasing then they are neither strictly increasing or decreasing
• So set strict too boolean:
• loop from idx 1:
  
  • Check if previous idx is < than previous
    
    • decreasing = False
  • Check if previous idx is > than previous
    
    • increasing = False
• return either if true

Question 5

Longest Peak

Answer 5

O(N) Time | O(1) space

Pattern:

• Set a variable for longestPeak and for I = 1
• Loop while I is less than second last:
  
  • find peak by seeing if leftidx or rightidx is decreasing
  • If not continue, increment i
  • else, loop through left side and right side, by setting left idx 2 away and right idx 2 away
    
    • check if they are strictly decreasing
  • Get the peak length by minus right to left - 1
  • Update longest
  • set i to rightIdx

Question 6

Array of Products

Answer 6

O(N) time | O(N) Space

Pattern:

• create a products array with all 1s
• create a running left product
• loop incrementally, make product[i] = running product, multiply the running product with array[i]
• create a running right product
• loop incrementally, make product[i] multiply by the running product, multiply the running product with array[i]
• return products

Question 7

First Duplicate Value

Answer 7

O(N) time | O(N) space

Pattern:

• Create a set as seen
• Loop through the array
  
  • If the num is in seen, return it
  • add num into seen
• return -1

Question 8

Spiral Traverse

Answer 8

O(N) Time | O(N) Space

Pattern:

• [Row] [Col]
• Set four pointers at each corner of the matrix
• Loop while opposite pointers are smaller or equal to each other
  
  • loop through col, left to right, add result
  • loop through row, up to down, add result (skips starting, to avoid double count
  • Reverse loop through col, right to left, add result (skips ending)
    
    • breaks if startrow = endrow to avoid odd counts
  • Reverse loop through col, down to up, add result (skips starting)
    
    • breaks if startCol = endCol to avoid odd counts
  • incre/decrement based on pointers

Question 9

Find Kth Largest Value in BST

Answer 9

O(N) Time | O(N) Space

Pattern:

• Since BST is left < right for every node,
• InorderTravse and append into an array
• return array[len(array)-kth]

Question 10

Merge Overlapping Intervals

Answer 10

O(N log N) Time | O(N) Space

Pattern:

• Sort the intervals
• Have a currentInterval, since it is an array, it is mutable
• Loop through sortedIntervals:
  
  • If currentEnd ≥ nextStart, then set currentInterval to nextEnd
  • else: set currentInterval to next interval and add interval to result

Question 11

Validate BST

Answer 11

O(N) time | O(Depth) space

Pattern:

• Use a helper function that sets minValue and maxValue to their infinities.
• Recursively traverse using helper function:
  
  • If the node is none, return True
  • if the node value is smaller than minValue return false
  • if the node value is greater or equal to maxValue return false
  • traverse left node with current value as new maxValue
  • traverse right node with current value as new minValue
  • return true if both are true

Question 12

Min Height BST

Answer 12

O(N) Time | O(N) Space

Pattern:

• Create a helper function for recursive call
• Base condition: if right < left
  
  • Find mid index of array
  • Create BST node with mid index
  • Recursively call BST node left and right with helper
  • Return BST node

Question 13

BST Construction: Insert()

Answer 13

O(N) Time | O(1) Space

Pattern:

• Set the currentNode to self
• Loop:
  
  • If value is smaller / larger,
    
    • If left / right is none:
      
      • new BST node
    • If left / right is not none
      
      • set currentNode to left
• return BST

Question 14

BST Construction: Contains()

Answer 14

O(N) Time | O(1) Space

Pattern:

• set currentNode to the node
• Loop while currentNode is not None:
  
  • If smaller or larger, set currentNode to left or right
  • If they equal return True
• Else return false

Question 15

BST Construction: Remove()

Answer 15

O(N) Time | O(1) Space

Pattern:

• Also use a getMin to find the smallest
• Use a parent node for same depth swapping

Question 16

Invert Binary Tree

Answer 16

O(N) Time | O(Depth) Time

Pattern:

• Base Case: if tree is none, return
• Swap left and right
• Recursively call left and right

Question 17

Valid IP Address

Answer 17

O(N) Time | O (N) Space

Pattern:

• Split IP address into four parts, and traverse each part individually
• Traverse current index up to the min(len(str) or 4), for other traversals add prevIdx and up to min(len(str)-prevIdx, 4)
• Use a helper function compare if it is valid, if it is go to next part, and if it is second last part, append it to the result array.