Skip to Content
DifficultyMedium

Find First and Last Position of Element in Sorted Array 

  • Use binary search technique to find the first & last position of the target element
  • Modify the conditional logic accordingly to find the first & last position of the target
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  // if target is beyond the limits of nums
  if (target > nums.at(-1) || target < nums[0]) {
    return [-1, -1];
  }
 
  const firstPos = getFirstPos(nums, target);
  if (firstPos === -1) {
    // if start position is not present, it means the number itself is not present
    return [-1, -1];
  }
  const lastPos = getLastPos(nums, target, firstPos);
 
  return [firstPos, lastPos];
};
 
function getFirstPos(nums, target) {
  let left = 0, right = nums.length - 1;
  let firstPos = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (nums[mid] === target) {
      firstPos = mid;
      right = mid - 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return firstPos;
}
 
function getLastPos(nums, target, firstPos) {
  let left = firstPos, right = nums.length - 1;
  let lastPos = -1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (nums[mid] === target) {
      lastPos = mid;
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return lastPos;
}
Complexity
  • Time: O(log(n))
  • Space: O(1)

Search in Rotated Sorted Array 

  • Find which half is sorted and check if the target is within the sorted half
  • If the target is within the sorted half, update the search range accordingly
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0, right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] === target) {
      return mid;
    }
 
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
 
  return -1;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Find Minimum in Rotated Sorted Array 

  • Find which half is sorted and store the minimum value
  • Explore the unsorted half till completion
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0, right = nums.length - 1, min = Infinity;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[left] <= nums[mid]) {
      min = Math.min(min, nums[left]);
      left = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      right = mid - 1;
    }
  }
 
  return min;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Search in Rotated Sorted Array II 

  • Find which half is sorted and check if the target is within the sorted half
  • If the target is within the sorted half, update the search range accordingly
  • If left, mid, and right are the same, move the left and right pointers
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
  let left = 0, right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid] === target) {
      return true;
    }
 
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left += 1;
      right -= 1;
    } else if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
 
  return false;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Reverse Words in a String 

  • Convert the string into an array of words and push the array of words (except empty space)
  • Reverse the resultant array and covert the array into string with space between words
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  let words = s.split(' ');
  let result = [];
  for (const word of words) {
    if (word.length) {
      result.push(word);
    }
  }
  return result.reverse().join(' ');
};
Complexity
  • Time: O(n)
  • Space: O(n)

Find Minimum in Rotated Sorted Array II 

  • Find which half is sorted and store the minimum value
  • Explore the unsorted half till completion
  • If left, mid, and right are the same, move the left and right pointers
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0, right = nums.length - 1;
  let min = Infinity;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      min = Math.min(min, nums[mid]);
      left += 1;
      right -= 1;
    } else if (nums[left] <= nums[mid]) {
      min = Math.min(min, nums[left]);
      left = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      right = mid - 1;
    }
  }
 
  return min;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Find Peak Element 

  • Use binary search to find if mid is a peak. If mid is not a peak, move towards the direction of the greater element
  • If mid ends at the first or last element, consider it as a peak
/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
  let left = 0, right = nums.length - 1, mid;
 
  while (left <= right) {
    mid = left + Math.floor((right - left) / 2);
 
    if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
      return mid;
    }
 
    if (nums[mid - 1] > nums[mid]) {
      right = mid - 1;
    } else if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;
    } else {
      // edge case where mid is the first/last element
      return mid;
    }
  }
 
  return mid;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Delete Node in a Linked List 

  • Copy the data from the successor node into the current node to be deleted.
  • Update the next pointer of the current node to reference the next pointer of the successor node.
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
node.val=node.next.val;
node.next=node.next.next;
};
Complexity
  • Time: O(1)
  • Space: O(1)

Find All Anagrams in a String 

  • Use Sliding window technique and check the every window is Anagram or not
  • if any window is Anagram, add its index to “res” array
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let res = [];
    let pCount = {};
    let sCount = {};
    let pLen = p.length;
    let sLen = s.length;
 
    // Populate the frequency count for the pattern p
    for (let char of p) {
        pCount[char] = (pCount[char] || 0) + 1;
    }
 
    // Initialize the frequency count for the first window of size p in s
    for (let i = 0; i < pLen; i++) {
        sCount[s[i]] = (sCount[s[i]] || 0) + 1;
    }
 
    // Compare the frequency count of the first window
    if (isSameCount(pCount, sCount)) {
        res.push(0);
    }
 
    // Slide the window over string s
    for (let i = pLen; i < sLen; i++) {
        // Add the new character to the current window count
        sCount[s[i]] = (sCount[s[i]] || 0) + 1;
        // Remove the character that is no longer in the window
        let startChar = s[i - pLen];
        if (sCount[startChar] > 1) {
            sCount[startChar]--;
        } else {
            delete sCount[startChar];
        }
        // Compare the frequency count of the current window
        if (isSameCount(pCount, sCount)) {
            res.push(i - pLen + 1);
        }
    }
 
    return res;
};
 
// Helper function to compare two frequency count objects
const isSameCount = function(count1, count2) {
    if (Object.keys(count1).length !== Object.keys(count2).length) {
        return false;
    }
    for (let key in count1) {
        if (count1[key] !== count2[key]) {
            return false;
        }
    }
    return true;
};
Complexity
  • Time: O(n)
    • The sliding window ensures that each character in s is processed only once.
    • The comparison of frequency counts is efficient and does not depend on the length of s.
  • Space: O(1)
    • The space used by the frequency count objects is limited to the number of distinct characters in p and s, which is constant (26 letters for lowercase English letters).

Kth Missing Positive Number 

  • Find the index of the lower bound of the missing number using binary search
  • Return the missing number by adding the k to the index
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function (arr, k) {
  let left = 0, right = arr.length - 1;
  let ans = arr.length;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const missingCount = arr[mid] - (mid + 1);
 
    // find smallest index of missing number greater than k
    if (k <= missingCount) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans + k; // arr[ans] + k - (arr[ans] - (ans + 1)) = kth missing number
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Two Sum II - Input Array Is Sorted 

  • As the array is sorted, we can use two pointers approach to find the sum of two numbers
  • If the sum of the two numbers is equal to the target, return the indices
  • If the sum is less than the target, move the left pointer to the right else move the right pointer to the left
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  let i = 0, j = numbers.length - 1;
 
  while (i < j) {
    const sum = numbers[i] + numbers[j];
 
    if (sum === target) {
      return [i + 1, j + 1];
    } else if (target < sum) {
      j--;
    } else if (target > sum) {
      i++;
    }
  }
};
Complexity
  • Time: O(n)
  • Space: O(1)

Koko Eating Bananas 

  • Use binary search to find the if mid is the minimum eating time
  • If time is less than or equal to h, update the answer and move towards the left
  • If time is greater than h, move towards the right
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
  let max = Math.max(...piles); // max possible count of bananas eaten per hour
  let left = 0, right = max, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const time = piles.reduce((acc, bananas) => acc + Math.ceil(bananas / mid), 0);
 
    if (time <= h) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
Complexity
  • Time: O(n log(Max(piles)))
  • Space: O(1)

Validate Stack Sequences 

  • Create a stack and loop through the pushed elements
  • If the element popped is encountered loop through the array popped and find the point where it is not equal
  /**
   * @param {int[] , int[]} pushed, popped
   * @return {boolean}
   */
  public boolean validateStackSequences(int[] pushed, int[] popped) {
    // start from pushed and check if it is in popped 
    // just follow the instructions, if not encpuntered just return false 
    int pop =0;
    Stack<Integer> stack = new Stack<>();
    for(int i=0; i<pushed.length ; i++) {
      stack.add(pushed[i]);         
      if(pushed[i]==popped[pop]) {
        for(int j=pop ; j<popped.length; j++) {
          if(!stack.isEmpty() &&  stack.peek()==popped[j]){
            pop++;
            stack.pop();
          } else {
            break;
          }
        }
      }
    }
    return stack.isEmpty();
  }
Complexity
  • Time: O(n)
  • Space: O(n)

Kth Largest Element in an Array 

  • Use PriorityQueue to save all the values in as a max heap
  • Dequeue k times to get the kth largest element
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const maxPQ = new MaxPriorityQueue();
 
  for (const num of nums) {
    maxPQ.enqueue(num, num);
  }
 
  while (k > 1) {
    maxPQ.dequeue();
    k--;
  }
 
  return maxPQ.front();
};
Complexity
  • Time: O(n * log(n))
  • Space: O(n)

Minimum Number of Days to Make m Bouquets 

  • Use binary search to find the if mid is the days to make m bouquets
  • If bouquets are greater than or equal to m, update the answer and move towards the left
  • If bouquets are less than m, move towards the right
/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var minDays = function (bloomDay, m, k) {
  if (m * k > bloomDay.length) {
    return -1;
  }
 
  let max = Math.max(...bloomDay); // max possible days
  let left = 0, right = max, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const bouquets = getBouquets(bloomDay, mid, m, k);
 
    if (bouquets >= m) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function getBouquets(bloomDay, mid, m, k) {
  let bouquets = 0, flowers = 0;
  
  for (let i = 0; i < bloomDay.length; i++) {
    // add flowers to bouquet if bloomed or reset
    flowers = bloomDay[i] <= mid ? flowers + 1 : 0
 
    // if enough flowers in a bouquet
    if (flowers === k) {
      bouquets += 1;
      flowers = 0;
    }
 
    // if enough bouquets
    if (bouquets === m) {
      break;
    }
  }
 
  return bouquets;
}
Complexity
  • Time: O(n log(Max(days)))
  • Space: O(1)

Find the Smallest Divisor Given a Threshold 

  • Use binary search to find the divisor if it satisfies the threshold
  • If sum is mo than threshold, move towards the right else move towards the left
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function (nums, threshold) {
  const max = Math.max(...nums);
  let left = 1, right = max, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const sum = divisorSum(nums, mid);
 
    if (sum <= threshold) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function divisorSum(nums, div) {
  let sum = 0;
  for (const val of nums) {
    sum += Math.ceil(val / div);
  }
  return sum;
}
Complexity
  • Time: O(n log(Max(nums)))
  • Space: O(1)

Capacity To Ship Packages Within D Days 

  • Use binary search to find the capacity with min & max as the max weight & total weight respectively
  • If the days to ship is less than or equal to the given days, move towards the left else move towards the right
/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (weights, days) {
  const [totalWeight, maxWeight] = getTotalAndMax(weights);
  let left = maxWeight, right = totalWeight;
  let ans = totalWeight;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const daysToShip = getDaysToShip(weights, mid);
 
    if (daysToShip <= days) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
 
function getTotalAndMax(arr) {
  let sum = 0, max = 0;
 
  for (const item of arr) {
    sum += item;
    if (max < item) {
      max = item;
    }
  }
 
  return [sum, max];
}
 
function getDaysToShip(weights, shipCapacity) {
  let days = 1, capacity = 0;
  for (const weight of weights) {
    if (capacity + weight > shipCapacity) {
      days += 1;
      capacity = 0;
    }
 
    capacity += weight;
  }
 
  return days;
}
Complexity
  • Time: O(n log(Sum(weights)))
  • Space: O(1)

Magnetic Force Between Two Balls 

  • Using binary search, set the left as 1 and right as the maximum distance between the balls
  • Check if the placements are possible with the given distance and continue till you find the maximum distance
  • Popularly known as the Aggressive Cows  problem
/**
 * @param {number[]} position
 * @param {number} m
 * @return {number}
 */
var maxDistance = function (positions, m) {
  positions.sort((a, b) => a - b);
  let left = 1,
    right = positions.at(-1) - positions.at(0);
 
  // placed in the 2 extreme end of the array
  if (m === 2) {
    return right;
  }
 
  let ans;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const isPossible = checkPlacements(positions, m, mid);
 
    if (isPossible) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return ans;
};
 
function checkPlacements(arr, m, distance) {
  let prev = arr[0],
    count = 1;
 
  for (let i = 1; i < arr.length; i++) {
    // if the gap is maintained
    if (arr[i] - prev >= distance) {
      count += 1;
      prev = arr[i];
    }
 
    // if placements are complete
    if (count === m) {
      return true;
    }
  }
 
  return false;
}
Complexity
  • Time: O(n log(n))
  • Space: O(1)

Asteroid Collision 

  • Start from left of the array, if the asteroid is positive, push it to the stack
  • If the asteroid is negative, keep popping from the stack until the stack is empty or the top of the stack is positive
/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function (asteroids) {
  const left = [], right = [];
 
  for (const asteroid of asteroids) {
    // when a right moving asteroid comes
    if (asteroid > 0) {
      left.push(asteroid);
      continue;
    }
 
    // when left moving asteroid destroys the possible right moving asteroids
    while (left.length && left.at(-1) < -asteroid) {
      left.pop();
    }
 
    // for the remaining right moving asteroid (may be equal or greater than the left moving destroyer)
    if (left.length) {
      if (left.at(-1) === -asteroid) {
        left.pop();
      }
      continue;
    }
 
    // if left moving asteroid wins
    right.push(asteroid);
  }
 
  return right.concat(left);
};
Complexity
  • Time: O(n)
  • Space: O(n)

Making File Names Unique 

  • Save all the file names in a map with their frequency & if a file name is already present, append a number to it
  • Continue until a unique file name is found and update the map with the new file name as well and its frequency
/**
 * @param {string[]} names
 * @return {string[]}
 */
var getFolderNames = function (names) {
  const freq = new Map();
 
  for (let i = 0; i < names.length; i++) {
    let key = names[i];
    let count = freq.get(key) ?? 0;
 
    while (freq.has(key)) {
      key = names[i] + `(${++count})`;
    }
 
    freq.set(key, 0);
    freq.set(names[i], count);
    names[i] = key;
  }
 
  return names;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Score After Flipping Matrix 

  • Flip each row if it has more 0 in the first column (MSB will give the maximum value)
  • For each column, maximize the number of 1s by flipping the column if it has more 0s than 1s
/**
 * @param {number[][]} grid
 * @return {number}
 */
var matrixScore = function (grid) {
  const m = grid.length, n = grid[0].length;
  let sum = (1 << (n - 1)) * m; // Set the MSB to 1 for each row
 
  for (let j = 1; j < n; j++) {
    // Count the number of 1s in the column
    let count = 0;
 
    for (let i = 0; i < m; i++) {
      // Flip the column if that row MSB was flipped
      count += grid[i][0] ? grid[i][j] : 1 - grid[i][j];
    }
 
    // Flip the column if it has more 0s than 1s
    sum += (1 << (n - 1 - j)) * Math.max(count, m - count);
  }
 
  return sum;
};
Complexity
  • Time: O(m * n)
  • Space: O(1)
Last updated on
EasyHard