Check Array Pairs Divisible by K

🎯

Check Array Pairs Divisible by K

mediumHASH_MAPAmazonGoogleFacebook

Imagine you have a list of socks, and you want to pair them so that the sum of the sizes of each pair is divisible by a given number K. Can you check if such pairing is possible for all socks?

💡 This problem is about pairing elements based on a condition involving divisibility. Beginners often struggle because they try to pair elements directly instead of tracking remainders and their complements, which is the key insight.

📋

Problem Statement

Given an array of integers nums and an integer k, determine if it is possible to pair all elements of the array such that the sum of each pair is divisible by k. Return true if such a pairing exists, otherwise false.

1 ≤ nums.length ≤ 10^51 ≤ k ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"nums = [1,2,3,4,5,10,6,7,8,9], k = 5"

Outputtrue

Pairs like (1,4), (2,3), (5,10), (6,9), (7,8) all sum to multiples of 5.

Input"nums = [1,2,3,4,5,6], k = 7"

Outputtrue

Pairs (1,6), (2,5), (3,4) sum to multiples of 7.

Input"nums = [1,2,3,4,5], k = 3"

Outputfalse

No way to pair all elements to have sums divisible by 3.

• Array length is odd → false
• All elements are zero and k divides zero → true
• Elements with remainder 0 must be even in count → false if odd
• Large values with negative numbers → handle modulo correctly

⚠️

Common Mistakes

Not checking if array length is even

Incorrectly returns true for odd length arrays

✅ Add a check at the start to return false if length is odd

Not handling negative numbers correctly in modulo

Remainders become negative, causing wrong frequency counts

✅ Adjust modulo with ((num % k) + k) % k to ensure positive remainder

Not checking remainder 0 frequency is even

Fails on inputs where remainder 0 elements cannot be paired

✅ Explicitly check freq[0] % 2 == 0 before proceeding

Ignoring the special case when k is even and remainder k/2 frequency is odd

Incorrectly returns true when pairing is impossible

✅ Check freq[k/2] % 2 == 0 when k is even

Using frequency array without considering large k values

Memory issues or inefficient for large k

✅ Use hash map for frequency counting when k is large or sparse

🧠

Brute Force (Nested Loops Checking All Pairs)

💡 This approach exists to build intuition by trying all possible pairings, which helps understand the problem's constraints and why a better approach is needed.

Intuition

Try every possible pair of elements and check if their sum is divisible by k. If all elements can be paired this way without reuse, return true.

Algorithm

1. Check if array length is even; if not, return false immediately.
2. Use a boolean array to mark elements as paired or not.
3. For each unpaired element, try to find another unpaired element such that their sum is divisible by k.
4. If all elements can be paired, return true; otherwise, false.

💡 This algorithm is hard to see as efficient because it tries all pairs, which grows quickly with input size.

</>

Code

def canArrange(nums, k):
    n = len(nums)
    if n % 2 != 0:
        return False
    used = [False] * n
    for i in range(n):
        if used[i]:
            continue
        found_pair = False
        for j in range(i + 1, n):
            if not used[j] and (nums[i] + nums[j]) % k == 0:
                used[i] = True
                used[j] = True
                found_pair = True
                break
        if not found_pair:
            return False
    return True

# Driver code
if __name__ == '__main__':
    print(canArrange([1,2,3,4,5,10,6,7,8,9], 5))  # True
    print(canArrange([1,2,3,4,5,6], 7))  # True
    print(canArrange([1,2,3,4,5], 3))  # False

Line Notes

if n % 2 != 0:If array length is odd, pairing all elements is impossible

used = [False] * nTrack which elements have been paired to avoid reuse

for i in range(n):Iterate over each element to find a pair

if not used[j] and (nums[i] + nums[j]) % k == 0:Check if sum of pair is divisible by k and both unused

import java.util.*;
public class Solution {
    public static boolean canArrange(int[] nums, int k) {
        int n = nums.length;
        if (n % 2 != 0) return false;
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            boolean foundPair = false;
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && (nums[i] + nums[j]) % k == 0) {
                    used[i] = true;
                    used[j] = true;
                    foundPair = true;
                    break;
                }
            }
            if (!foundPair) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canArrange(new int[]{1,2,3,4,5,10,6,7,8,9}, 5)); // true
        System.out.println(canArrange(new int[]{1,2,3,4,5,6}, 7)); // true
        System.out.println(canArrange(new int[]{1,2,3,4,5}, 3)); // false
    }
}

Line Notes

if (n % 2 != 0) return false;Odd length means impossible to pair all elements

boolean[] used = new boolean[n];Track paired elements to prevent reuse

for (int i = 0; i < n; i++) {Outer loop to pick first element for pairing

if (!used[j] && (nums[i] + nums[j]) % k == 0)Check if pair sums to multiple of k and both unused

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

bool canArrange(vector<int>& nums, int k) {
    int n = nums.size();
    if (n % 2 != 0) return false;
    vector<bool> used(n, false);
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        bool foundPair = false;
        for (int j = i + 1; j < n; j++) {
            if (!used[j] && (nums[i] + nums[j]) % k == 0) {
                used[i] = true;
                used[j] = true;
                foundPair = true;
                break;
            }
        }
        if (!foundPair) return false;
    }
    return true;
}

int main() {
    vector<int> nums1 = {1,2,3,4,5,10,6,7,8,9};
    cout << (canArrange(nums1, 5) ? "true" : "false") << endl; // true
    vector<int> nums2 = {1,2,3,4,5,6};
    cout << (canArrange(nums2, 7) ? "true" : "false") << endl; // true
    vector<int> nums3 = {1,2,3,4,5};
    cout << (canArrange(nums3, 3) ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

if (n % 2 != 0) return false;Cannot pair all if odd number of elements

vector<bool> used(n, false);Keep track of which elements are already paired

for (int i = 0; i < n; i++) {Select each element to find a pair

if (!used[j] && (nums[i] + nums[j]) % k == 0)Check if sum divisible by k and both unused

function canArrange(nums, k) {
    const n = nums.length;
    if (n % 2 !== 0) return false;
    const used = new Array(n).fill(false);
    for (let i = 0; i < n; i++) {
        if (used[i]) continue;
        let foundPair = false;
        for (let j = i + 1; j < n; j++) {
            if (!used[j] && (nums[i] + nums[j]) % k === 0) {
                used[i] = true;
                used[j] = true;
                foundPair = true;
                break;
            }
        }
        if (!foundPair) return false;
    }
    return true;
}

// Test cases
console.log(canArrange([1,2,3,4,5,10,6,7,8,9], 5)); // true
console.log(canArrange([1,2,3,4,5,6], 7)); // true
console.log(canArrange([1,2,3,4,5], 3)); // false

Line Notes

if (n % 2 !== 0) return false;Odd length arrays cannot be fully paired

const used = new Array(n).fill(false);Track which elements have been paired

for (let i = 0; i < n; i++) {Iterate over elements to find pairs

if (!used[j] && (nums[i] + nums[j]) % k === 0)Check if sum divisible by k and both unused

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We check pairs for each element, leading to roughly n*(n-1)/2 checks. The used array takes O(n) space.

💡 For n=20, this means about 190 checks, which is manageable, but for n=100000 it becomes billions of checks and is too slow.

Interview Verdict: TLE

This approach times out on large inputs, showing the need for a more efficient method.

🧠

Better Approach Using Frequency Map of Remainders

💡 This approach introduces the key insight of tracking remainders modulo k and their frequencies, which reduces the problem to matching complementary remainders.

Intuition

Instead of pairing elements directly, track how many elements have each remainder mod k. Pairs must come from complementary remainders that sum to k.

Algorithm

1. Check if array length is even; if not, return false.
2. Create a frequency map of nums[i] % k for all elements, adjusting modulo for negatives.
3. For remainder 0, check if count is even.
4. For each remainder r from 1 to (k-1)//2, check if freq[r] equals freq[k-r].
5. If k is even, check freq[k/2] is even.
6. If all checks pass, return true; else false.

💡 This algorithm is easier to implement and understand once you grasp the remainder pairing logic.

</>

Code

def canArrange(nums, k):
    if len(nums) % 2 != 0:
        return False
    freq = [0] * k
    for num in nums:
        r = ((num % k) + k) % k  # Adjust modulo for negative numbers
        freq[r] += 1
    if freq[0] % 2 != 0:
        return False
    for r in range(1, (k + 1) // 2):
        if freq[r] != freq[k - r]:
            return False
    if k % 2 == 0 and freq[k // 2] % 2 != 0:
        return False
    return True

# Driver code
if __name__ == '__main__':
    print(canArrange([1,2,3,4,5,10,6,7,8,9], 5))  # True
    print(canArrange([1,2,3,4,5,6], 7))  # True
    print(canArrange([1,2,3,4,5], 3))  # False

Line Notes

if len(nums) % 2 != 0:Odd length means no perfect pairing possible

freq = [0] * kInitialize frequency array for remainders

r = ((num % k) + k) % k # Adjust modulo for negative numbersCalculate remainder for each element, handling negatives correctly

if freq[0] % 2 != 0:Remainder 0 elements must be even to pair among themselves

import java.util.*;
public class Solution {
    public static boolean canArrange(int[] nums, int k) {
        if (nums.length % 2 != 0) return false;
        int[] freq = new int[k];
        for (int num : nums) {
            int r = ((num % k) + k) % k;
            freq[r]++;
        }
        if (freq[0] % 2 != 0) return false;
        for (int r = 1; r <= k / 2; r++) {
            if (freq[r] != freq[k - r]) return false;
        }
        if (k % 2 == 0 && freq[k / 2] % 2 != 0) return false;
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canArrange(new int[]{1,2,3,4,5,10,6,7,8,9}, 5)); // true
        System.out.println(canArrange(new int[]{1,2,3,4,5,6}, 7)); // true
        System.out.println(canArrange(new int[]{1,2,3,4,5}, 3)); // false
    }
}

Line Notes

if (nums.length % 2 != 0) return false;Odd length arrays cannot be fully paired

int[] freq = new int[k];Frequency array to count remainders

int r = ((num % k) + k) % k;Handle negative numbers correctly for remainder

if (freq[0] % 2 != 0) return false;Remainder zero elements must be even in count

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

bool canArrange(vector<int>& nums, int k) {
    int n = nums.size();
    if (n % 2 != 0) return false;
    vector<int> freq(k, 0);
    for (int num : nums) {
        int r = ((num % k) + k) % k;
        freq[r]++;
    }
    if (freq[0] % 2 != 0) return false;
    for (int r = 1; r <= k / 2; r++) {
        if (freq[r] != freq[k - r]) return false;
    }
    if (k % 2 == 0 && freq[k / 2] % 2 != 0) return false;
    return true;
}

int main() {
    vector<int> nums1 = {1,2,3,4,5,10,6,7,8,9};
    cout << (canArrange(nums1, 5) ? "true" : "false") << endl; // true
    vector<int> nums2 = {1,2,3,4,5,6};
    cout << (canArrange(nums2, 7) ? "true" : "false") << endl; // true
    vector<int> nums3 = {1,2,3,4,5};
    cout << (canArrange(nums3, 3) ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

if (n % 2 != 0) return false;Odd number of elements means no perfect pairing

vector<int> freq(k, 0);Frequency vector to count remainders

int r = ((num % k) + k) % k;Modulo operation adjusted for negative numbers

if (freq[0] % 2 != 0) return false;Elements with remainder zero must be even in count

function canArrange(nums, k) {
    if (nums.length % 2 !== 0) return false;
    const freq = new Array(k).fill(0);
    for (const num of nums) {
        let r = ((num % k) + k) % k;
        freq[r]++;
    }
    if (freq[0] % 2 !== 0) return false;
    for (let r = 1; r < (k + 1) / 2; r++) {
        if (freq[r] !== freq[k - r]) return false;
    }
    if (k % 2 === 0 && freq[k / 2] % 2 !== 0) return false;
    return true;
}

// Test cases
console.log(canArrange([1,2,3,4,5,10,6,7,8,9], 5)); // true
console.log(canArrange([1,2,3,4,5,6], 7)); // true
console.log(canArrange([1,2,3,4,5], 3)); // false

Line Notes

if (nums.length % 2 !== 0) return false;Odd length arrays cannot be fully paired

const freq = new Array(k).fill(0);Frequency array to count remainders

let r = ((num % k) + k) % k;Modulo adjusted for negative numbers

if (freq[0] % 2 !== 0) return false;Remainder zero elements must be even in count

⏱

Complexity

TimeO(n + k)

SpaceO(k)

We iterate once over nums to build frequency map (O(n)) and then check pairs in O(k). Space is O(k) for frequency array.

💡 For n=100000 and k=100000, this is efficient and feasible in interviews.

Interview Verdict: Accepted

This approach passes all tests efficiently and is the recommended solution.

🧠

Optimal Approach Using Hash Map for Frequency Counting

💡 This approach uses a hash map instead of an array to handle large or sparse k values and negative numbers more flexibly.

Intuition

Use a hash map to count frequencies of remainders mod k, then verify complementary remainder counts match for pairing.

Algorithm

1. Return false if array length is odd.
2. Create a hash map to count frequencies of nums[i] % k, adjusting modulo for negatives.
3. Check if frequency of remainder 0 is even.
4. For each remainder r in the map (excluding 0), check if freq[r] equals freq[k-r].
5. If k is even, check freq[k/2] is even.
6. Return true if all conditions hold.

💡 This approach generalizes the frequency array method to handle any k and negative values robustly.

</>

Code

def canArrange(nums, k):
    if len(nums) % 2 != 0:
        return False
    freq = {}
    for num in nums:
        r = ((num % k) + k) % k  # Adjust modulo for negative numbers
        freq[r] = freq.get(r, 0) + 1
    if freq.get(0, 0) % 2 != 0:
        return False
    for r in freq:
        if r != 0:
            complement = (k - r) % k
            if freq.get(r, 0) != freq.get(complement, 0):
                return False
    if k % 2 == 0 and freq.get(k // 2, 0) % 2 != 0:
        return False
    return True

# Driver code
if __name__ == '__main__':
    print(canArrange([1,2,3,4,5,10,6,7,8,9], 5))  # True
    print(canArrange([1,2,3,4,5,6], 7))  # True
    print(canArrange([1,2,3,4,5], 3))  # False

Line Notes

freq = {}Use dictionary to count remainder frequencies dynamically

r = ((num % k) + k) % k # Adjust modulo for negative numbersCalculate remainder for each element, handling negatives correctly

freq[r] = freq.get(r, 0) + 1Increment frequency count safely

if freq.get(0, 0) % 2 != 0:Check even count for remainder zero elements

import java.util.*;
public class Solution {
    public static boolean canArrange(int[] nums, int k) {
        if (nums.length % 2 != 0) return false;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            int r = ((num % k) + k) % k;
            freq.put(r, freq.getOrDefault(r, 0) + 1);
        }
        if (freq.getOrDefault(0, 0) % 2 != 0) return false;
        for (int r : freq.keySet()) {
            if (r != 0) {
                int complement = (k - r) % k;
                if (!freq.getOrDefault(r, 0).equals(freq.getOrDefault(complement, 0))) return false;
            }
        }
        if (k % 2 == 0 && freq.getOrDefault(k / 2, 0) % 2 != 0) return false;
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canArrange(new int[]{1,2,3,4,5,10,6,7,8,9}, 5)); // true
        System.out.println(canArrange(new int[]{1,2,3,4,5,6}, 7)); // true
        System.out.println(canArrange(new int[]{1,2,3,4,5}, 3)); // false
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>();Use hash map for flexible remainder frequency counting

int r = ((num % k) + k) % k;Modulo adjusted for negative numbers

freq.put(r, freq.getOrDefault(r, 0) + 1);Increment frequency safely

if (freq.getOrDefault(0, 0) % 2 != 0) return false;Check even count for remainder zero

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

bool canArrange(vector<int>& nums, int k) {
    int n = nums.size();
    if (n % 2 != 0) return false;
    unordered_map<int, int> freq;
    for (int num : nums) {
        int r = ((num % k) + k) % k;
        freq[r]++;
    }
    if (freq[0] % 2 != 0) return false;
    for (auto& p : freq) {
        int r = p.first;
        if (r != 0) {
            int complement = (k - r) % k;
            if (freq[r] != freq[complement]) return false;
        }
    }
    if (k % 2 == 0 && freq[k / 2] % 2 != 0) return false;
    return true;
}

int main() {
    vector<int> nums1 = {1,2,3,4,5,10,6,7,8,9};
    cout << (canArrange(nums1, 5) ? "true" : "false") << endl; // true
    vector<int> nums2 = {1,2,3,4,5,6};
    cout << (canArrange(nums2, 7) ? "true" : "false") << endl; // true
    vector<int> nums3 = {1,2,3,4,5};
    cout << (canArrange(nums3, 3) ? "true" : "false") << endl; // false
    return 0;
}

Line Notes

unordered_map<int, int> freq;Hash map for remainder frequency counting

int r = ((num % k) + k) % k;Modulo adjusted for negative numbers

freq[r]++;Increment frequency count

if (freq[0] % 2 != 0) return false;Check even count for remainder zero

function canArrange(nums, k) {
    if (nums.length % 2 !== 0) return false;
    const freq = new Map();
    for (const num of nums) {
        let r = ((num % k) + k) % k;
        freq.set(r, (freq.get(r) || 0) + 1);
    }
    if ((freq.get(0) || 0) % 2 !== 0) return false;
    for (const r of freq.keys()) {
        if (r !== 0) {
            const complement = (k - r) % k;
            if ((freq.get(r) || 0) !== (freq.get(complement) || 0)) return false;
        }
    }
    if (k % 2 === 0 && ((freq.get(k / 2) || 0) % 2 !== 0)) return false;
    return true;
}

// Test cases
console.log(canArrange([1,2,3,4,5,10,6,7,8,9], 5)); // true
console.log(canArrange([1,2,3,4,5,6], 7)); // true
console.log(canArrange([1,2,3,4,5], 3)); // false

Line Notes

const freq = new Map();Use Map for flexible remainder frequency counting

let r = ((num % k) + k) % k;Modulo adjusted for negative numbers

freq.set(r, (freq.get(r) || 0) + 1);Increment frequency count safely

if ((freq.get(0) || 0) % 2 !== 0) return false;Check even count for remainder zero

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate over nums once and use a hash map for frequencies. Checking pairs is O(n) in worst case.

💡 This approach is efficient even if k is large or sparse, and handles negative numbers gracefully.

Interview Verdict: Accepted

This is the most general and robust solution, suitable for all inputs.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the frequency map approach (Approach 2) is usually the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Frequency Array	O(n + k)	O(k)	No	N/A	Code this for small to moderate k values
3. Frequency Hash Map	O(n)	O(n)	No	N/A	Code this for large or negative inputs

💼

Interview Strategy

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

How to Present

Step 1: Clarify the problem and constraints, especially array length and value ranges.Step 2: Present the brute force approach to show understanding of the problem.Step 3: Explain the frequency remainder insight and implement the frequency array solution.Step 4: Discuss the hash map approach for large or negative inputs.Step 5: Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to identify the key insight of remainder pairing, handle edge cases, and optimize from brute force to efficient hash map solutions.

Common Follow-ups

• What if the array length is odd? → Return false immediately.
• How to handle negative numbers? → Use modulo adjustment to get positive remainders.

💡 These follow-ups test your understanding of problem constraints and modular arithmetic nuances.

🔍

Pattern Recognition

When to Use

1) Problem involves pairing elements; 2) Condition depends on sum divisible by k; 3) Need to track counts or frequencies; 4) Complementary pairs based on remainders.

Signature Phrases

sum divisible by kpair all elementsfrequency of remainderscomplement remainder

NOT This Pattern When

Problems that require subsequence or substring DP, or greedy without frequency tracking

Similar Problems

Two Sum - uses complement concept for sumsValid Anagram - frequency counting patternGroup Anagrams - grouping by key properties

Practice

1. You are given an integer array and a number k. You need to count the number of contiguous subarrays that contain exactly k odd numbers. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use dynamic programming to store counts of subarrays ending at each index with exactly k odd numbers.

B. Use a brute force nested loop to check all subarrays and count odd numbers.

C. Use a sliding window with two pointers to count subarrays with at most k and k-1 odd numbers and subtract.

D. Use a greedy approach to expand and shrink the window whenever the odd count exceeds k.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting subarrays with exactly k odd numbers efficiently.

2. Step 2: Evaluate approaches

   Brute force is O(n^2), DP is complex and not straightforward here, greedy alone doesn't guarantee correctness. Sliding window with two pointers counting at most k and k-1 odd numbers and subtracting is optimal and linear.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window approach runs in O(n) time [OK]

Hint: Sliding window with at most k counts is optimal [OK]

Common Mistakes:

• Thinking greedy alone solves it optimally
• Assuming DP is needed
• Using brute force for large inputs

2. You need to find the length of the longest substring in a string that contains at most two distinct characters. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a brute force approach checking all substrings with nested loops and counting distinct characters each time.

B. Use a sliding window with a frequency map to track character counts and adjust window size dynamically.

C. Use dynamic programming to store results of substrings and build up the solution.

D. Use a greedy approach that always picks the next character if it doesn't increase distinct count beyond two.

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest substring with at most two distinct characters, which suggests a variable-length window that expands and contracts based on distinct character count.

2. Step 2: Identify suitable algorithm

   Sliding window with a frequency map efficiently tracks character counts and distinct characters, allowing O(n) time complexity by adjusting window boundaries dynamically.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with frequency map is the classic optimal approach for this problem [OK]

Hint: Sliding window tracks distinct chars in O(n) time [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Confusing DP with substring problems
• Assuming greedy always works

3. Consider the following Python code implementing the optimal approach to count subarrays with bounded maximum:

def countAtMost(nums, bound):
    count = 0
    length = 0
    for num in nums:
        if num <= bound:
            length += 1
            count += length
        else:
            length = 0
    return count

def numSubarrayBoundedMax(nums, left, right):
    return countAtMost(nums, right) - countAtMost(nums, left - 1)

print(numSubarrayBoundedMax([2,1,4,3], 2, 3))

What is the output of this code?

easy

A. 4

B. 3

C. 5

D. 2

Solution

1. Step 1: Trace countAtMost(nums, right=3)

   nums=[2,1,4,3], bound=3 - num=2 ≤3: length=1, count=1 - num=1 ≤3: length=2, count=3 - num=4 >3: length=0 - num=3 ≤3: length=1, count=4 Total countAtMost=4

2. Step 2: Trace countAtMost(nums, left-1=1)

   nums=[2,1,4,3], bound=1 - num=2 >1: length=0 - num=1 ≤1: length=1, count=1 - num=4 >1: length=0 - num=3 >1: length=0 Total countAtMost=1 Calculate final: 4 - 1 = 3

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected count of valid subarrays [OK]

Hint: Subtract countsAtMost(right) and countsAtMost(left-1) [OK]

Common Mistakes:

• Off-by-one in bounds
• Miscounting length resets
• Confusing countAtMost results

4. What is the time complexity of the optimal prefix sum with hash map solution for finding the longest contiguous subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n) because each element is processed once with constant-time hash map operations

B. O(n) but with O(n²) space for storing all prefix sums

C. O(n log n) due to sorting or balanced tree operations in the hash map

D. O(n²) due to nested loops scanning subarrays

Solution

1. Step 1: Identify the single loop over the array

   The algorithm iterates once over n elements, updating prefix_sum and hash map.

2. Step 2: Confirm hash map operations are O(1) average

   Insertion and lookup in hash map are average O(1), so total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is O(n²), no sorting involved, space is O(n) not O(n²) [OK]

Hint: Hash map lookups are average O(1), single pass over array [OK]

Common Mistakes:

• Confusing brute force O(n²) with optimal
• Assuming hash map is O(log n)
• Overestimating space complexity

5. What is the time complexity of the optimal sliding window solution for the Minimum Operations to Reduce X to Zero problem, assuming the input array length is n?

medium

A. O(n^2) due to nested loops for adjusting window boundaries.

B. O(n) for the main loop plus O(n) for sum computations inside the loop.

C. O(n) because each element is visited at most twice by left and right pointers.

D. O(n log n) due to sorting or binary search steps.

Solution

1. Step 1: Analyze the main loop and window adjustments

   The right pointer moves from 0 to n-1 once, and the left pointer only moves forward when shrinking the window, so each element is visited at most twice.

2. Step 2: Confirm no nested loops causing quadratic time

   While loop inside the for loop advances left pointer without resetting, so total moves of left pointer ≤ n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window runs in linear time [OK]

Hint: Sliding window moves pointers linearly [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Forgetting that left pointer only moves forward
• Confusing sum computations as extra loops