Binary Search on Answer Technique in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Answer for Minimum Maximum Subarray Sum

What is the output of the following TypeScript code that uses binary search on answer to find the minimum largest sum among subarrays?

DSA Typescript

function canSplit(nums: number[], maxSum: number, m: number): boolean {
  let currentSum = 0, count = 1;
  for (const num of nums) {
    if (num > maxSum) return false;
    if (currentSum + num > maxSum) {
      count++;
      currentSum = num;
      if (count > m) return false;
    } else {
      currentSum += num;
    }
  }
  return true;
}

function splitArray(nums: number[], m: number): number {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canSplit(nums, mid, m)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

const nums = [7,2,5,10,8];
const m = 2;
console.log(splitArray(nums, m));

A 18

B 15

C 20

D 23

💡 Hint

Think about how the array can be split into 2 subarrays with minimum largest sum.

The function tries to find the smallest maximum subarray sum possible when splitting the array into m parts. For [7,2,5,10,8] and m=2, the minimum largest sum is 18, achieved by splitting as [7,2,5] and [10,8].

🧠 Conceptual

intermediate

Understanding Binary Search on Answer Technique

Which of the following best describes the main idea behind the binary search on answer technique?

A Using binary search to find the correct value in a sorted array directly.

B Using binary search to find the index of a target value in a linked list.

C Using binary search to sort an unsorted array efficiently.

D Using binary search over a range of possible answers to find the minimum or maximum value that satisfies a condition.

💡 Hint

Think about searching over a range of values, not array indices.

Binary search on answer searches over a range of possible answers (not array indices) to find the smallest or largest value that meets a problem's condition.

🔧 Debug

advanced

Identify the Bug in Binary Search on Answer Implementation

What is the bug in the following TypeScript code that tries to find the minimum maximum time to complete tasks by workers using binary search on answer?

DSA Typescript

function canComplete(tasks: number[], maxTime: number, workers: number): boolean {
  let currentTime = 0;
  let count = 1;
  for (const task of tasks) {
    if (task > maxTime) return false;
    if (currentTime + task > maxTime) {
      count++;
      currentTime = task;
      if (count > workers) return false;
    } else {
      currentTime += task;
    }
  }
  return true;
}

function minTime(tasks: number[], workers: number): number {
  let left = Math.max(...tasks);
  let right = tasks.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (canComplete(tasks, mid, workers)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

const tasks = [3, 6, 7, 11];
const workers = 2;
console.log(minTime(tasks, workers));

A The mid calculation should use (left + right + 1) / 2 to avoid infinite loop.

B The condition 'currentTime + task >= maxTime' should be 'currentTime + task > maxTime' to avoid extra worker count.

C The function should return false if tasks array is empty.

D The initial left boundary should be 0 instead of max task time.

💡 Hint

Check the condition that triggers a new worker assignment.

Using '>=' causes a new worker to be assigned even when currentTime + task equals maxTime, which is unnecessary and leads to incorrect results.

❓ Predict Output

advanced

Output of Binary Search on Answer for Aggressive Cows Problem

What is the output of the following TypeScript code that uses binary search on answer to place cows in stalls maximizing minimum distance?

DSA Typescript

function canPlaceCows(stalls: number[], distance: number, cows: number): boolean {
  let count = 1;
  let lastPosition = stalls[0];
  for (let i = 1; i < stalls.length; i++) {
    if (stalls[i] - lastPosition >= distance) {
      count++;
      lastPosition = stalls[i];
      if (count >= cows) return true;
    }
  }
  return false;
}

function aggressiveCows(stalls: number[], cows: number): number {
  stalls.sort((a, b) => a - b);
  let left = 1;
  let right = stalls[stalls.length - 1] - stalls[0];
  let result = 0;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (canPlaceCows(stalls, mid, cows)) {
      result = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
}

const stalls = [1, 2, 8, 4, 9];
const cows = 3;
console.log(aggressiveCows(stalls, cows));

A 4

B 5

C 3

D 6

💡 Hint

Think about placing cows with maximum minimum distance between them.

The maximum minimum distance to place 3 cows in stalls [1,2,4,8,9] is 3, placing cows at positions 1, 4, and 8.

🧠 Conceptual

expert

When to Use Binary Search on Answer Technique?

Which scenario is the best fit for applying binary search on answer technique?

A When the problem asks for an optimal numeric value that can be checked by a yes/no condition over a range.

B When you need to find an element in a sorted array by index.

C When you want to sort an array in O(n log n) time.

D When you need to traverse a tree in depth-first order.

💡 Hint

Think about searching over a range of possible answers with a feasibility check.

Binary search on answer is used when the answer is a number in a range and you can check if a candidate answer satisfies the problem's constraints.