Split Array Largest Sum

🎯

Split Array Largest Sum

hardBINARY_SEARCHAmazonGoogleFacebook

Imagine you have a long list of daily expenses and want to split them into a fixed number of months so that the maximum monthly expense is as small as possible.

💡 This problem asks you to split an array into subarrays to minimize the largest sum among them. Beginners often struggle because it’s not obvious how to efficiently find the minimal largest sum without checking all splits.

📋

Problem Statement

Given an array of non-negative integers nums and an integer m, split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Return this minimized largest sum.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^91 ≤ m ≤ min(50, nums.length)

💡

Example

Input"nums = [7,2,5,10,8], m = 2"

Output18

Split into [7,2,5] and [10,8], largest sums are 14 and 18, so answer is 18 which is minimal possible.

• m = 1 → output is sum of entire array
• m = length of nums → output is max element in nums
• nums contains zeros → zeros do not affect max sum but affect splits
• nums contains very large values → test handling of large sums without overflow

⚠️

Common Mistakes

Not setting low to max(nums) in binary search

Binary search may try impossible sums smaller than max element, causing incorrect results or infinite loops

✅ Initialize low = max(nums) to ensure feasibility

Incorrect greedy check by not resetting current sum properly

May count wrong number of splits, leading to wrong feasibility results

✅ Reset current sum to current element when starting new subarray

Off-by-one errors in binary search boundaries

Infinite loops or missing correct answer

✅ Use while(low < high) and update low or high correctly

Not handling large sums with appropriate data types

Integer overflow causing wrong answers or runtime errors

✅ Use long/long long or equivalent for sums

Trying to use DP or recursion without memoization for large inputs

Time limit exceeded or stack overflow

✅ Use binary search with greedy check instead

🧠

Brute Force (Pure Recursion / Nested Loops / etc.)

💡 Starting with brute force helps understand the problem deeply by exploring all possible splits, even though it’s inefficient.

Intuition

Try every possible way to split the array into m parts and calculate the largest sum for each split. The minimal among these is the answer.

Algorithm

1. Define a recursive function that takes the start index and number of splits left.
2. If only one split left, return sum of remaining elements.
3. Otherwise, try all possible split points from start to end.
4. For each split, recursively compute the largest sum for the remaining splits and take the minimal among all splits.

💡 The recursion explores all splits, which is conceptually simple but computationally expensive.

</>

Code

from typing import List

def splitArray(nums: List[int], m: int) -> int:
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]

    def dfs(start: int, splits: int) -> int:
        if splits == 1:
            return prefix[n] - prefix[start]
        min_largest = float('inf')
        for i in range(start + 1, n - splits + 2):
            left_sum = prefix[i] - prefix[start]
            right_largest = dfs(i, splits - 1)
            largest = max(left_sum, right_largest)
            min_largest = min(min_largest, largest)
        return min_largest

    return dfs(0, m)

# Driver code
if __name__ == '__main__':
    print(splitArray([7,2,5,10,8], 2))  # Expected output: 18

Line Notes

prefix = [0] * (n + 1)Create prefix sums for O(1) range sum queries

def dfs(start: int, splits: int) -> int:Recursive function to explore splits from start with splits left

if splits == 1:Base case: only one split means sum remaining elements

for i in range(start + 1, n - splits + 2):Try all possible split points ensuring enough elements remain

left_sum = prefix[i] - prefix[start]Sum of current subarray from start to i-1

right_largest = dfs(i, splits - 1)Recursively find largest sum for remaining splits

largest = max(left_sum, right_largest)Largest sum in this split configuration

min_largest = min(min_largest, largest)Keep track of minimal largest sum found

import java.util.*;

public class SplitArrayLargestSum {
    public static int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        return dfs(prefix, 0, m, n);
    }

    private static int dfs(int[] prefix, int start, int splits, int n) {
        if (splits == 1) {
            return prefix[n] - prefix[start];
        }
        int minLargest = Integer.MAX_VALUE;
        for (int i = start + 1; i <= n - splits + 1; i++) {
            int leftSum = prefix[i] - prefix[start];
            int rightLargest = dfs(prefix, i, splits - 1, n);
            int largest = Math.max(leftSum, rightLargest);
            minLargest = Math.min(minLargest, largest);
        }
        return minLargest;
    }

    public static void main(String[] args) {
        System.out.println(splitArray(new int[]{7,2,5,10,8}, 2)); // Expected: 18
    }
}

Line Notes

int[] prefix = new int[n + 1];Prefix sums for quick range sum calculation

private static int dfs(int[] prefix, int start, int splits, int n)Recursive helper to explore splits

if (splits == 1)Base case: sum remaining elements

for (int i = start + 1; i <= n - splits + 1; i++)Try all valid split points

int leftSum = prefix[i] - prefix[start];Sum of current subarray

int rightLargest = dfs(prefix, i, splits - 1, n);Recursive call for remaining splits

int largest = Math.max(leftSum, rightLargest);Largest sum in this split

minLargest = Math.min(minLargest, largest);Track minimal largest sum

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<int>& prefix, int start, int splits, int n) {
    if (splits == 1) {
        return prefix[n] - prefix[start];
    }
    int minLargest = INT_MAX;
    for (int i = start + 1; i <= n - splits + 1; i++) {
        int leftSum = prefix[i] - prefix[start];
        int rightLargest = dfs(prefix, i, splits - 1, n);
        int largest = max(leftSum, rightLargest);
        minLargest = min(minLargest, largest);
    }
    return minLargest;
}

int splitArray(vector<int>& nums, int m) {
    int n = nums.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return dfs(prefix, 0, m, n);
}

int main() {
    vector<int> nums = {7,2,5,10,8};
    cout << splitArray(nums, 2) << endl; // Expected: 18
    return 0;
}

Line Notes

vector<int> prefix(n + 1, 0);Prefix sums for O(1) subarray sums

int dfs(const vector<int>& prefix, int start, int splits, int n)Recursive function to try all splits

if (splits == 1)Base case: sum remaining elements

for (int i = start + 1; i <= n - splits + 1; i++)Try all valid split points

int leftSum = prefix[i] - prefix[start];Sum of current subarray

int rightLargest = dfs(prefix, i, splits - 1, n);Recursive call for remaining splits

int largest = max(leftSum, rightLargest);Largest sum in this split

minLargest = min(minLargest, largest);Track minimal largest sum

function splitArray(nums, m) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    function dfs(start, splits) {
        if (splits === 1) {
            return prefix[n] - prefix[start];
        }
        let minLargest = Infinity;
        for (let i = start + 1; i <= n - splits + 1; i++) {
            const leftSum = prefix[i] - prefix[start];
            const rightLargest = dfs(i, splits - 1);
            const largest = Math.max(leftSum, rightLargest);
            minLargest = Math.min(minLargest, largest);
        }
        return minLargest;
    }

    return dfs(0, m);
}

// Test
console.log(splitArray([7,2,5,10,8], 2)); // Expected: 18

Line Notes

const prefix = new Array(n + 1).fill(0);Prefix sums for quick subarray sums

function dfs(start, splits)Recursive function to explore splits

if (splits === 1)Base case: sum remaining elements

for (let i = start + 1; i <= n - splits + 1; i++)Try all valid split points

const leftSum = prefix[i] - prefix[start];Sum of current subarray

const rightLargest = dfs(i, splits - 1);Recursive call for remaining splits

const largest = Math.max(leftSum, rightLargest);Largest sum in this split

minLargest = Math.min(minLargest, largest);Track minimal largest sum

⏱

Complexity

TimeO(n^m)

SpaceO(m) for recursion stack

For each of the m-1 splits, we try up to n positions, leading to exponential time.

💡 For n=10 and m=3, this means roughly 10^3=1000 operations, but for n=100, m=5 it explodes to 100^5=10 billion operations.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and forms the basis for optimization.

🧠

Binary Search on Answer Space with Greedy Check

💡 This approach uses binary search on the range of possible largest sums and a greedy check to verify feasibility, drastically improving efficiency.

Intuition

The minimal largest sum lies between max(nums) and sum(nums). We binary search this range and check if we can split into m subarrays without exceeding the mid sum.

Algorithm

1. Set low to max element and high to sum of all elements.
2. While low < high, compute mid = (low + high) // 2.
3. Check if array can be split into ≤ m subarrays with max sum ≤ mid using a greedy approach.
4. If feasible, move high to mid; else move low to mid + 1.
5. Return low as the minimal largest sum.

💡 Binary search narrows down the answer space, and greedy check quickly verifies feasibility.

</>

Code

from typing import List

def splitArray(nums: List[int], m: int) -> int:
    def can_split(max_sum: int) -> bool:
        current_sum = 0
        splits = 1
        for num in nums:
            if current_sum + num > max_sum:
                splits += 1
                current_sum = num
                if splits > m:
                    return False
            else:
                current_sum += num
        return True

    low, high = max(nums), sum(nums)
    while low < high:
        mid = (low + high) // 2
        if can_split(mid):
            high = mid
        else:
            low = mid + 1
    return low

# Driver code
if __name__ == '__main__':
    print(splitArray([7,2,5,10,8], 2))  # Expected output: 18

Line Notes

def can_split(max_sum: int) -> bool:Check if array can be split with max subarray sum ≤ max_sum

if current_sum + num > max_sum:Start new subarray if adding num exceeds max_sum

if splits > m:If more than m splits needed, not feasible

low, high = max(nums), sum(nums)Initialize binary search bounds

while low < high:Binary search loop to narrow answer

if can_split(mid):If feasible, try smaller max sum

else: low = mid + 1If not feasible, increase lower bound

public class SplitArrayLargestSum {
    public static boolean canSplit(int[] nums, int m, long maxSum) {
        int splits = 1;
        long currentSum = 0;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                splits++;
                currentSum = num;
                if (splits > m) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }

    public static int splitArray(int[] nums, int m) {
        int maxNum = 0;
        long sum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
            sum += num;
        }

        long low = maxNum, high = sum;
        while (low < high) {
            long mid = low + (high - low) / 2;
            if (canSplit(nums, m, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return (int) low;
    }

    public static void main(String[] args) {
        System.out.println(splitArray(new int[]{7,2,5,10,8}, 2)); // Expected: 18
    }
}

Line Notes

public static boolean canSplit(int[] nums, int m, long maxSum)Greedy feasibility check for maxSum

if (currentSum + num > maxSum)Start new subarray if sum exceeds maxSum

if (splits > m) return false;More splits than allowed means not feasible

long low = maxNum, high = sum;Binary search bounds initialization

while (low < high)Binary search loop

if (canSplit(nums, m, mid))If feasible, try smaller maxSum

else low = mid + 1;If not feasible, increase lower bound

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canSplit(const vector<int>& nums, int m, long long maxSum) {
    int splits = 1;
    long long currentSum = 0;
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            splits++;
            currentSum = num;
            if (splits > m) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

int splitArray(vector<int>& nums, int m) {
    int maxNum = *max_element(nums.begin(), nums.end());
    long long sum = 0;
    for (int num : nums) sum += num;

    long long low = maxNum, high = sum;
    while (low < high) {
        long long mid = low + (high - low) / 2;
        if (canSplit(nums, m, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return (int)low;
}

int main() {
    vector<int> nums = {7,2,5,10,8};
    cout << splitArray(nums, 2) << endl; // Expected: 18
    return 0;
}

Line Notes

bool canSplit(const vector<int>& nums, int m, long long maxSum)Greedy feasibility check function

if (currentSum + num > maxSum)Start new subarray if sum exceeds maxSum

if (splits > m) return false;Too many splits means not feasible

long long low = maxNum, high = sum;Initialize binary search bounds

while (low < high)Binary search loop

if (canSplit(nums, m, mid))If feasible, try smaller maxSum

else low = mid + 1;If not feasible, increase lower bound

function splitArray(nums, m) {
    function canSplit(maxSum) {
        let splits = 1, currentSum = 0;
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                splits++;
                currentSum = num;
                if (splits > m) return false;
            } else {
                currentSum += num;
            }
        }
        return true;
    }

    let low = Math.max(...nums);
    let high = nums.reduce((a,b) => a + b, 0);

    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canSplit(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Test
console.log(splitArray([7,2,5,10,8], 2)); // Expected: 18

Line Notes

function canSplit(maxSum)Greedy feasibility check for maxSum

if (currentSum + num > maxSum)Start new subarray if sum exceeds maxSum

if (splits > m) return false;Too many splits means not feasible

let low = Math.max(...nums);Initialize lower bound as max element

let high = nums.reduce((a,b) => a + b, 0);Initialize upper bound as sum of all elements

while (low < high)Binary search loop

if (canSplit(mid))If feasible, try smaller maxSum

else low = mid + 1;If not feasible, increase lower bound

⏱

Complexity

TimeO(n log(sum(nums)))

SpaceO(1)

Binary search runs in log of sum(nums) range, each feasibility check is O(n).

💡 For n=10^5 and sum around 10^9, this is about 30 * 10^5 = 3 million operations, efficient enough.

Interview Verdict: Accepted

This is the standard efficient solution for this problem and is expected in interviews.

🧠

Binary Search with Prefix Sum Optimization

💡 This approach is similar to the previous but uses prefix sums to speed up sum calculations inside the greedy check.

Intuition

Use prefix sums to quickly compute subarray sums during the greedy feasibility check, avoiding repeated summations.

Algorithm

1. Compute prefix sums of nums.
2. Binary search between max element and total sum.
3. For each mid, greedily find subarrays by binary searching prefix sums to find max subarray sums ≤ mid.
4. Count how many subarrays are needed; if more than m, increase low; else decrease high.
5. Return low as minimal largest sum.

💡 Prefix sums combined with binary search inside the greedy check reduce time spent summing subarrays.

</>

Code

from typing import List
import bisect

def splitArray(nums: List[int], m: int) -> int:
    n = len(nums)
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    def can_split(max_sum: int) -> bool:
        count = 0
        start = 0
        while start < n:
            # binary search to find max end where prefix[end] - prefix[start] <= max_sum
            end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1
            count += 1
            start = end
            if count > m:
                return False
        return True

    low, high = max(nums), prefix[-1]
    while low < high:
        mid = (low + high) // 2
        if can_split(mid):
            high = mid
        else:
            low = mid + 1
    return low

# Driver code
if __name__ == '__main__':
    print(splitArray([7,2,5,10,8], 2))  # Expected output: 18

Line Notes

prefix = [0]Initialize prefix sums array

prefix.append(prefix[-1] + num)Build prefix sums for O(1) subarray sums

end = bisect.bisect_right(prefix, prefix[start] + max_sum, lo=start+1) - 1Find furthest subarray end with sum ≤ max_sum

count += 1Count one subarray formed

if count > m: return FalseToo many subarrays means not feasible

low, high = max(nums), prefix[-1]Binary search bounds initialization

while low < high:Binary search loop

if can_split(mid):If feasible, try smaller max_sum

import java.util.*;

public class SplitArrayLargestSum {
    public static boolean canSplit(int[] nums, int m, long maxSum, long[] prefix) {
        int count = 0, n = nums.length, start = 0;
        while (start < n) {
            int low = start + 1, high = n, pos = start;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (prefix[mid] - prefix[start] <= maxSum) {
                    pos = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            count++;
            start = pos;
            if (count > m) return false;
        }
        return true;
    }

    public static int splitArray(int[] nums, int m) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        int maxNum = 0;
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
            maxNum = Math.max(maxNum, nums[i]);
        }

        long low = maxNum, high = prefix[n];
        while (low < high) {
            long mid = low + (high - low) / 2;
            if (canSplit(nums, m, mid, prefix)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return (int) low;
    }

    public static void main(String[] args) {
        System.out.println(splitArray(new int[]{7,2,5,10,8}, 2)); // Expected: 18
    }
}

Line Notes

long[] prefix = new long[n + 1];Prefix sums for O(1) subarray sums

while (start < n)Iterate to form subarrays greedily

binary search inside while loopFind max subarray end with sum ≤ maxSum

count++Count one subarray formed

if (count > m) return false;Too many subarrays means not feasible

long low = maxNum, high = prefix[n];Binary search bounds initialization

while (low < high)Binary search loop

if (canSplit(nums, m, mid, prefix))If feasible, try smaller maxSum

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canSplit(const vector<int>& nums, int m, long long maxSum, const vector<long long>& prefix) {
    int count = 0, n = nums.size(), start = 0;
    while (start < n) {
        int low = start + 1, high = n, pos = start;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (prefix[mid] - prefix[start] <= maxSum) {
                pos = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        count++;
        start = pos;
        if (count > m) return false;
    }
    return true;
}

int splitArray(vector<int>& nums, int m) {
    int n = nums.size();
    vector<long long> prefix(n + 1, 0);
    int maxNum = 0;
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
        maxNum = max(maxNum, nums[i]);
    }

    long long low = maxNum, high = prefix[n];
    while (low < high) {
        long long mid = low + (high - low) / 2;
        if (canSplit(nums, m, mid, prefix)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return (int)low;
}

int main() {
    vector<int> nums = {7,2,5,10,8};
    cout << splitArray(nums, 2) << endl; // Expected: 18
    return 0;
}

Line Notes

vector<long long> prefix(n + 1, 0);Prefix sums for O(1) subarray sums

while (start < n)Greedy subarray formation loop

binary search inside while loopFind max subarray end with sum ≤ maxSum

count++Count one subarray formed

if (count > m) return false;Too many subarrays means not feasible

long long low = maxNum, high = prefix[n];Binary search bounds initialization

while (low < high)Binary search loop

if (canSplit(nums, m, mid, prefix))If feasible, try smaller maxSum

function splitArray(nums, m) {
    const prefix = [0];
    for (const num of nums) {
        prefix.push(prefix[prefix.length - 1] + num);
    }

    function canSplit(maxSum) {
        let count = 0, start = 0, n = nums.length;
        while (start < n) {
            let low = start + 1, high = n, pos = start;
            while (low <= high) {
                let mid = Math.floor((low + high) / 2);
                if (prefix[mid] - prefix[start] <= maxSum) {
                    pos = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            count++;
            start = pos;
            if (count > m) return false;
        }
        return true;
    }

    let low = Math.max(...nums);
    let high = prefix[prefix.length - 1];

    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canSplit(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Test
console.log(splitArray([7,2,5,10,8], 2)); // Expected: 18

Line Notes

const prefix = [0];Initialize prefix sums array

prefix.push(prefix[prefix.length - 1] + num);Build prefix sums for O(1) subarray sums

while (start < n)Greedy subarray formation loop

binary search inside while loopFind max subarray end with sum ≤ maxSum

count++Count one subarray formed

if (count > m) return false;Too many subarrays means not feasible

let low = Math.max(...nums);Initialize lower bound

let high = prefix[prefix.length - 1];Initialize upper bound

⏱

Complexity

TimeO(n log n log(sum(nums)))

SpaceO(n)

Binary search on answer space with an inner binary search on prefix sums for each subarray, increasing complexity slightly.

💡 This is slower than the previous approach but still efficient for large inputs.

Interview Verdict: Accepted

This approach is a valid optimization but usually unnecessary compared to the simpler greedy check.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always implement the binary search with greedy check approach for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^m)	O(m) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Binary Search on Answer Space with Greedy Check	O(n log(sum(nums)))	O(1)	No	Yes, with extra tracking	Code this approach
3. Binary Search with Prefix Sum Optimization	O(n log n log(sum(nums)))	O(n)	No	Yes	Optional optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the binary search approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force approach to show understanding.Introduce binary search on answer space and the greedy feasibility check.Write clean, efficient code for the binary search approach.Test with edge cases and explain your testing.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test & Explain: 7min. Total ~25min

What the Interviewer Tests

Your ability to identify binary search on answer space, implement a greedy check, and optimize for large inputs.

Common Follow-ups

• What if m = 1? → Return sum of entire array.
• What if m = length of nums? → Return max element.
• Can you reconstruct the actual split? → Yes, by tracking split points during greedy check.
• What if nums contains negative numbers? → Problem constraints disallow negatives; approach needs adjustment otherwise.

💡 These follow-ups test your understanding of edge cases, reconstruction, and problem constraints.

🔍

Pattern Recognition

When to Use

1) Asked to minimize/maximize a value related to subarray sums; 2) Splitting array into m parts; 3) Constraints too large for brute force; 4) Problem hints at binary search on answer space.

Signature Phrases

'split array into m subarrays''minimize the largest sum among these subarrays'

NOT This Pattern When

Classic DP partition problems without binary search, or problems requiring exact partition counts without minimization.

Similar Problems

Capacity To Ship Packages Within D Days - similar binary search on answer spaceKoko Eating Bananas - binary search on minimum feasible speedSplit Array into Consecutive Subsequences - related splitting problem

Practice

1. Consider the following Python code using bisect to count occurrences of a target in a sorted array. What is the output when nums = [1, 2, 2, 3] and target = 2?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace bisect_left for target=2

   bisect_left(nums, 2) returns index 1 (first 2 in array).

2. Step 2: Trace bisect_left for target+1=3

   bisect_left(nums, 3) returns index 3 (first 3 in array).

3. Step 3: Calculate count

   Count = right - left = 3 - 1 = 2 occurrences.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Indices 1 and 2 are 2's in array [OK]

Hint: bisect_left finds first occurrence index [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Off-by-one errors in index subtraction
• Using bisect_right for target+1 incorrectly

2. The following code attempts to find the minimum in a rotated sorted array without duplicates. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line calculating mid = (left + right) // 2

B. Line calculating prev = mid - 1

C. Line checking if nums[mid] < nums[prev]

D. Line updating left = mid + 1

Solution

1. Step 1: Identify prev index calculation

   Prev is set to mid - 1 without modulo, which can be -1 if mid=0, causing out-of-bound or incorrect access.

2. Step 2: Correct calculation uses modulo to wrap around

   Prev should be (mid - 1 + n) % n to handle circular indexing safely.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Prev index must wrap around to avoid negative index [OK]

Hint: Prev index must use modulo to avoid negative index [OK]

Common Mistakes:

• Forgetting modulo on prev index
• Assuming mid > 0 always
• Ignoring circular array property

3. Examine the following code snippet intended to search a target in a 2D matrix using binary search treating it as a 1D array. Identify the line containing the subtle bug that can cause incorrect results or runtime errors.

medium

A. Line 6: row, col = divmod(mid, n)

B. Line 3: left, right = 0, m * n - 1

C. Line 1: m, n = len(matrix), len(matrix[0])

D. Line 9: left = mid + 1

Solution

1. Step 1: Check for empty matrix handling

   The code does not check if matrix or matrix[0] is empty before accessing len(matrix[0]), which can cause runtime errors.

2. Step 2: Verify other lines

   Lines for binary search boundaries and index mapping are correct assuming valid input.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing empty matrix check leads to crash [OK]

Hint: Always check for empty matrix or empty rows before accessing indices [OK]

Common Mistakes:

• Forgetting empty input checks
• Incorrect index mapping
• Wrong boundary updates

4. Suppose you want to find the first occurrence of a target value in a sorted array that may contain duplicates. Which modification to the classic binary search algorithm correctly achieves this?

hard

A. Return the first index where nums[mid] == target and check if previous element is different or mid == 0

B. Return any index where nums[mid] == target without further checks

C. Use linear search after binary search to find first occurrence

D. Modify binary search to always move low to mid + 1 when nums[mid] == target

Solution

1. Step 1: Understand problem with duplicates

   Classic binary search returns any matching index, not necessarily first occurrence.

2. Step 2: Modify binary search to check if mid is first occurrence

   When nums[mid] == target, check if mid == 0 or nums[mid-1] != target; if not, continue searching left half.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ensures first occurrence by verifying previous element [OK]

Hint: Check previous element to find first occurrence [OK]

Common Mistakes:

• Returning any occurrence
• Linear search after binary search wastes time
• Moving low forward on match loses first occurrence

5. Suppose the problem is modified so that the input array arr can contain negative numbers and zero, and you still need to find the kth positive missing number (positive integers missing from the array). Which of the following changes to the optimal binary search approach is correct?

hard

A. Modify the missing count calculation to be arr[mid] - (mid + 1) + offset, where offset accounts for negative numbers.

B. No change needed; the existing binary search works as is because it only depends on indices and values.

C. Filter out non-positive numbers first, then apply the binary search approach on the filtered positive array.

D. Use the brute force linear scan approach instead, as binary search cannot handle negative numbers.

Solution

1. Step 1: Understand the problem modification

   Negative numbers and zero do not affect the count of missing positive integers, but they disrupt the assumption that arr contains only positive sorted numbers.

2. Step 2: Adjust the input for binary search

   Filtering out non-positive numbers creates a sorted array of positive integers, restoring the problem's original assumptions and enabling correct binary search.

3. Step 3: Reject other options

   No change (B) fails because negative numbers break missing count logic; offset (C) is ambiguous and error-prone; brute force (D) is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Filtering preserves correctness and efficiency [OK]

Hint: Filter positives before binary search [OK]

Common Mistakes:

• Assuming binary search works without filtering
• Trying to adjust missing count with offsets
• Switching to brute force unnecessarily