Minimize Deviation in Array

🎯

Minimize Deviation in Array

hardHEAPAmazonGoogle

Imagine you have a set of project budgets that can be adjusted by doubling or halving under certain rules, and you want to minimize the difference between the largest and smallest budgets to optimize capital allocation.

💡 This problem is about cleverly adjusting numbers to minimize their range. Beginners often struggle because the problem involves conditional transformations and maintaining dynamic order statistics, which is tricky without the right data structure.

📋

Problem Statement

Given an array nums of n positive integers, you can perform two types of operations any number of times on any element: if the element is even, divide it by 2; if the element is odd, multiply it by 2. Return the minimum possible deviation of the array after performing any number of operations.

1 ≤ n ≤ 10^51 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1, 2, 3, 4]"

Output1

Transform 1 to 2 (odd → double), 3 to 6 (odd → double), then halve 6 to 3, and halve 4 to 2. The array becomes [2, 2, 3, 2], deviation = 3 - 2 = 1.

• All elements are the same → output 0
• Array with a single element → output 0
• Array with all odd numbers → doubling once then halving as needed
• Array with very large numbers near 10^9 → test performance and correctness

⚠️

Common Mistakes

Not normalizing odd numbers by doubling first

Leads to missing possible smaller deviations

✅ Always double odd numbers at the start to make all elements even

Using min-heap instead of max-heap to track maximum element

Cannot efficiently access and reduce the maximum element

✅ Use max-heap or simulate max-heap with negative values in min-heap

Not updating the minimum element after halving max

Incorrect deviation calculation leading to wrong answers

✅ Track and update minimum element whenever max is halved and reinserted

Trying to halve odd numbers or double even numbers arbitrarily

Violates problem constraints and leads to invalid states

✅ Only halve even numbers and double odd numbers as per problem rules

Not handling large input sizes efficiently

Solution times out or runs out of memory

✅ Use efficient data structures and avoid brute force

🧠

Brute Force (Exhaustive Search with Recursion)

💡 This approach tries all possible transformations on each element to find the minimal deviation. It is impractical for large inputs but helps understand the problem deeply.

Intuition

Try every possible combination of doubling odd numbers and halving even numbers recursively, then compute the deviation for each combination to find the minimum.

Algorithm

1. Define a recursive function that tries all valid transformations on each element.
2. At each recursion level, transform the current element if possible and recurse to the next.
3. Keep track of the minimum and maximum elements in the current array state.
4. Return the minimum deviation found after exploring all transformations.

💡 The recursion tree grows exponentially, making it hard to visualize and inefficient, but it guarantees correctness by exploring all states.

</>

Code

from math import inf

def min_deviation_brute(nums):
    n = len(nums)
    min_dev = inf

    def dfs(i, arr):
        nonlocal min_dev
        if i == n:
            current_dev = max(arr) - min(arr)
            if current_dev < min_dev:
                min_dev = current_dev
            return

        val = arr[i]
        # Try without change
        dfs(i + 1, arr)

        # If even, try halving
        if val % 2 == 0:
            arr[i] = val // 2
            dfs(i + 1, arr)
            arr[i] = val

        # If odd, try doubling
        if val % 2 == 1:
            arr[i] = val * 2
            dfs(i + 1, arr)
            arr[i] = val

    dfs(0, nums[:])
    return min_dev

# Driver code
if __name__ == '__main__':
    print(min_deviation_brute([1,2,3,4]))  # Expected output: 1

Line Notes

def dfs(i, arr):Defines recursive function to explore transformations at index i

if i == n:Base case: all elements processed, compute deviation

dfs(i + 1, arr)Recurse without changing current element

if val % 2 == 0:If even, try halving to explore that transformation

import java.util.*;

public class MinDeviationBrute {
    static int minDev = Integer.MAX_VALUE;
    static int n;

    public static void dfs(int i, int[] arr) {
        if (i == n) {
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int val : arr) {
                max = Math.max(max, val);
                min = Math.min(min, val);
            }
            minDev = Math.min(minDev, max - min);
            return;
        }

        int val = arr[i];
        // Without change
        dfs(i + 1, arr);

        // If even, try halving
        if (val % 2 == 0) {
            arr[i] = val / 2;
            dfs(i + 1, arr);
            arr[i] = val;
        }

        // If odd, try doubling
        if (val % 2 == 1) {
            arr[i] = val * 2;
            dfs(i + 1, arr);
            arr[i] = val;
        }
    }

    public static int minimumDeviation(int[] nums) {
        n = nums.length;
        dfs(0, nums);
        return minDev;
    }

    public static void main(String[] args) {
        System.out.println(minimumDeviation(new int[]{1,2,3,4})); // Expected: 1
    }
}

Line Notes

public static void dfs(int i, int[] arr)Recursive function exploring transformations at index i

if (i == n)Base case: all elements processed, compute deviation

dfs(i + 1, arr);Recurse without changing current element

if (val % 2 == 0)Try halving if element is even

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

int minDev = INT_MAX;
int n;

void dfs(int i, vector<int>& arr) {
    if (i == n) {
        int maxVal = INT_MIN, minVal = INT_MAX;
        for (int val : arr) {
            maxVal = max(maxVal, val);
            minVal = min(minVal, val);
        }
        minDev = min(minDev, maxVal - minVal);
        return;
    }

    int val = arr[i];
    // Without change
    dfs(i + 1, arr);

    // If even, try halving
    if (val % 2 == 0) {
        arr[i] = val / 2;
        dfs(i + 1, arr);
        arr[i] = val;
    }

    // If odd, try doubling
    if (val % 2 == 1) {
        arr[i] = val * 2;
        dfs(i + 1, arr);
        arr[i] = val;
    }
}

int minimumDeviation(vector<int>& nums) {
    n = nums.size();
    dfs(0, nums);
    return minDev;
}

int main() {
    vector<int> nums = {1,2,3,4};
    cout << minimumDeviation(nums) << endl; // Expected: 1
    return 0;
}

Line Notes

void dfs(int i, vector<int>& arr)Recursive function exploring all transformations at index i

if (i == n)Base case: all elements processed, compute deviation

dfs(i + 1, arr);Recurse without changing current element

if (val % 2 == 0)Try halving if element is even

function minimumDeviation(nums) {
    let minDev = Infinity;
    const n = nums.length;

    function dfs(i, arr) {
        if (i === n) {
            const maxVal = Math.max(...arr);
            const minVal = Math.min(...arr);
            minDev = Math.min(minDev, maxVal - minVal);
            return;
        }

        const val = arr[i];
        // Without change
        dfs(i + 1, arr);

        // If even, try halving
        if (val % 2 === 0) {
            arr[i] = val / 2;
            dfs(i + 1, arr);
            arr[i] = val;
        }

        // If odd, try doubling
        if (val % 2 === 1) {
            arr[i] = val * 2;
            dfs(i + 1, arr);
            arr[i] = val;
        }
    }

    dfs(0, nums.slice());
    return minDev;
}

// Test
console.log(minimumDeviation([1,2,3,4])); // Expected: 1

Line Notes

function dfs(i, arr)Recursive helper to explore transformations at index i

if (i === n)Base case: all elements processed, compute deviation

dfs(i + 1, arr);Recurse without changing current element

if (val % 2 === 0)Try halving if element is even

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each element can be transformed in up to two ways, leading to exponential combinations.

💡 For n=20, this means over a million combinations, which is too large to run in reasonable time.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness.

🧠

Sorting + Two Pointer / Set Based Approach

💡 This approach tries to reduce the search space by normalizing the array and using a data structure to track min and max efficiently, but it still lacks the optimal heap-based optimization.

Intuition

Double all odd numbers to make all elements even, then try to reduce the maximum by halving it while tracking the minimum to minimize deviation.

Algorithm

1. Double all odd numbers to make the array elements even.
2. Sort the array to easily track minimum and maximum.
3. Iteratively halve the maximum element if it is even and update the minimum accordingly.
4. Keep track of the minimum deviation found during the process.

💡 Sorting helps to quickly find min and max, but updating min after halving max requires careful tracking.

</>

Code

def minimumDeviation(nums):
    nums = [x*2 if x % 2 else x for x in nums]
    nums.sort()
    import bisect
    min_dev = nums[-1] - nums[0]
    while nums[-1] % 2 == 0:
        max_val = nums.pop()
        max_val //= 2
        bisect.insort(nums, max_val)
        min_dev = min(min_dev, nums[-1] - nums[0])
    return min_dev

# Driver code
if __name__ == '__main__':
    print(minimumDeviation([1,2,3,4]))  # Expected output: 1

Line Notes

nums = [x*2 if x % 2 else x for x in nums]Normalize all numbers to even by doubling odd numbers

nums.sort()Sort to track min and max easily

while nums[-1] % 2 == 0:While max is even, try halving it to reduce deviation

bisect.insort(nums, max_val)Insert halved max back maintaining sorted order

import java.util.*;

public class MinDeviationSort {
    public static int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        int minVal = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 1) num *= 2;
            set.add(num);
            minVal = Math.min(minVal, num);
        }

        int minDev = Integer.MAX_VALUE;
        while (true) {
            int maxVal = set.last();
            minDev = Math.min(minDev, maxVal - minVal);
            if (maxVal % 2 == 0) {
                set.remove(maxVal);
                maxVal /= 2;
                set.add(maxVal);
                minVal = Math.min(minVal, maxVal);
            } else {
                break;
            }
        }
        return minDev;
    }

    public static void main(String[] args) {
        System.out.println(minimumDeviation(new int[]{1,2,3,4})); // Expected: 1
    }
}

Line Notes

TreeSet<Integer> set = new TreeSet<>();Use TreeSet to maintain sorted order and quick min/max access

if (num % 2 == 1) num *= 2;Normalize odd numbers by doubling

int maxVal = set.last();Get current maximum element

if (maxVal % 2 == 0)Halve max if even to reduce deviation

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

int minimumDeviation(vector<int>& nums) {
    multiset<int> s;
    int minVal = INT_MAX;
    for (int num : nums) {
        if (num % 2 == 1) num *= 2;
        s.insert(num);
        minVal = min(minVal, num);
    }

    int minDev = INT_MAX;
    while (true) {
        int maxVal = *s.rbegin();
        minDev = min(minDev, maxVal - minVal);
        if (maxVal % 2 == 0) {
            s.erase(prev(s.end()));
            maxVal /= 2;
            s.insert(maxVal);
            minVal = min(minVal, maxVal);
        } else {
            break;
        }
    }
    return minDev;
}

int main() {
    vector<int> nums = {1,2,3,4};
    cout << minimumDeviation(nums) << endl; // Expected: 1
    return 0;
}

Line Notes

multiset<int> s;Use multiset to maintain sorted elements with duplicates

if (num % 2 == 1) num *= 2;Normalize odd numbers by doubling

int maxVal = *s.rbegin();Get maximum element efficiently

if (maxVal % 2 == 0)Halve max if even to reduce deviation

function minimumDeviation(nums) {
    const sorted = [];
    for (let num of nums) {
        if (num % 2 === 1) num *= 2;
        sorted.push(num);
    }
    sorted.sort((a,b) => a - b);

    let minVal = sorted[0];
    let minDev = sorted[sorted.length - 1] - minVal;

    while (sorted[sorted.length - 1] % 2 === 0) {
        let maxVal = sorted.pop();
        maxVal /= 2;
        // Insert maxVal back in sorted order
        let left = 0, right = sorted.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (sorted[mid] < maxVal) left = mid + 1;
            else right = mid;
        }
        sorted.splice(left, 0, maxVal);
        minVal = Math.min(minVal, maxVal);
        minDev = Math.min(minDev, sorted[sorted.length - 1] - minVal);
    }
    return minDev;
}

// Test
console.log(minimumDeviation([1,2,3,4])); // Expected: 1

Line Notes

if (num % 2 === 1) num *= 2;Normalize odd numbers by doubling

sorted.sort((a,b) => a - b);Sort array to track min and max easily

while (sorted[sorted.length - 1] % 2 === 0)While max is even, halve it to reduce deviation

sorted.splice(left, 0, maxVal);Insert halved max back maintaining sorted order

⏱

Complexity

TimeO(n log n * log M)

SpaceO(n)

Sorting takes O(n log n), and halving max element can happen up to O(log M) times where M is max element.

💡 For n=10^5 and max element ~10^9, this approach is efficient enough for interviews.

Interview Verdict: Accepted

This approach is efficient and acceptable in interviews but can be improved with a max-heap for better clarity.

🧠

Optimal Approach Using Max-Heap

💡 This approach uses a max-heap to always reduce the current maximum element if possible, while tracking the minimum element to minimize deviation efficiently.

Intuition

Normalize all numbers to even by doubling odds, push them into a max-heap, then repeatedly pop the max and halve it if even, updating the minimum and deviation until max is odd.

Algorithm

1. Double all odd numbers to make all elements even.
2. Push all elements into a max-heap and track the minimum element.
3. Pop the maximum element from the heap.
4. Update the minimum deviation with current max - min.
5. If the max is even, halve it and push back into the heap, update minimum if needed.
6. Repeat until the max element is odd, then return the minimum deviation.

💡 The heap ensures we always operate on the largest element, and halving it reduces deviation stepwise.

</>

Code

import heapq

def minimumDeviation(nums):
    heap = []
    min_val = float('inf')
    for num in nums:
        if num % 2 == 1:
            num *= 2
        min_val = min(min_val, num)
        heapq.heappush(heap, -num)  # max heap by pushing negative

    min_dev = float('inf')
    while True:
        max_val = -heapq.heappop(heap)
        min_dev = min(min_dev, max_val - min_val)
        if max_val % 2 == 0:
            max_val //= 2
            min_val = min(min_val, max_val)
            heapq.heappush(heap, -max_val)
        else:
            break
    return min_dev

# Driver code
if __name__ == '__main__':
    print(minimumDeviation([1,2,3,4]))  # Expected output: 1

Line Notes

heapq.heappush(heap, -num)Push negative to simulate max-heap using min-heap

min_val = min(min_val, num)Track minimum element seen so far

max_val = -heapq.heappop(heap)Pop current maximum element

if max_val % 2 == 0:If max is even, halve it to reduce deviation

import java.util.*;

public class MinDeviationHeap {
    public static int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int minVal = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 1) num *= 2;
            maxHeap.add(num);
            minVal = Math.min(minVal, num);
        }

        int minDev = Integer.MAX_VALUE;
        while (true) {
            int maxVal = maxHeap.poll();
            minDev = Math.min(minDev, maxVal - minVal);
            if (maxVal % 2 == 0) {
                maxVal /= 2;
                minVal = Math.min(minVal, maxVal);
                maxHeap.add(maxVal);
            } else {
                break;
            }
        }
        return minDev;
    }

    public static void main(String[] args) {
        System.out.println(minimumDeviation(new int[]{1,2,3,4})); // Expected: 1
    }
}

Line Notes

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());Max-heap to always get largest element

if (num % 2 == 1) num *= 2;Normalize odd numbers by doubling

int maxVal = maxHeap.poll();Extract current maximum element

if (maxVal % 2 == 0)Halve max if even to reduce deviation

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

int minimumDeviation(vector<int>& nums) {
    priority_queue<int> maxHeap;
    int minVal = INT_MAX;
    for (int num : nums) {
        if (num % 2 == 1) num *= 2;
        maxHeap.push(num);
        minVal = min(minVal, num);
    }

    int minDev = INT_MAX;
    while (true) {
        int maxVal = maxHeap.top(); maxHeap.pop();
        minDev = min(minDev, maxVal - minVal);
        if (maxVal % 2 == 0) {
            maxVal /= 2;
            minVal = min(minVal, maxVal);
            maxHeap.push(maxVal);
        } else {
            break;
        }
    }
    return minDev;
}

int main() {
    vector<int> nums = {1,2,3,4};
    cout << minimumDeviation(nums) << endl; // Expected: 1
    return 0;
}

Line Notes

priority_queue<int> maxHeap;Max-heap to always access largest element

if (num % 2 == 1) num *= 2;Normalize odd numbers by doubling

int maxVal = maxHeap.top(); maxHeap.pop();Pop current maximum element

if (maxVal % 2 == 0)Halve max if even to reduce deviation

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0 && this.heap[this.parent(i)] < this.heap[i]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 0) return null;
        const max = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.heapify(0);
        }
        return max;
    }
    heapify(i) {
        let largest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
        if (right < this.heap.length && this.heap[right] > this.heap[largest]) largest = right;
        if (largest !== i) {
            this.swap(i, largest);
            this.heapify(largest);
        }
    }
    top() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }
}

function minimumDeviation(nums) {
    const maxHeap = new MaxHeap();
    let minVal = Infinity;
    for (let num of nums) {
        if (num % 2 === 1) num *= 2;
        maxHeap.push(num);
        minVal = Math.min(minVal, num);
    }

    let minDev = Infinity;
    while (true) {
        let maxVal = maxHeap.pop();
        minDev = Math.min(minDev, maxVal - minVal);
        if (maxVal % 2 === 0) {
            maxVal /= 2;
            minVal = Math.min(minVal, maxVal);
            maxHeap.push(maxVal);
        } else {
            break;
        }
    }
    return minDev;
}

// Test
console.log(minimumDeviation([1,2,3,4])); // Expected: 1

Line Notes

class MaxHeapCustom max-heap implementation for largest element extraction

if (num % 2 === 1) num *= 2;Normalize odd numbers by doubling

let maxVal = maxHeap.pop();Pop current maximum element

if (maxVal % 2 === 0)Halve max if even to reduce deviation

⏱

Complexity

TimeO(n log n * log M)

SpaceO(n)

Each element is pushed and popped from the heap up to O(log M) times, M being max element.

💡 This approach is efficient for large inputs and is the preferred solution in interviews.

Interview Verdict: Accepted

This is the optimal and most interview-friendly approach for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 The max-heap approach is the best to implement in interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Sorting + Two Pointer / Set	O(n log n * log M)	O(n)	No	Yes	Good to mention, acceptable to code if heap is unfamiliar
3. Optimal Max-Heap	O(n log n * log M)	O(n)	No	Yes	Preferred approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and operations allowed.Step 2: Explain brute force approach to show understanding.Step 3: Discuss sorting and normalization to reduce complexity.Step 4: Present the max-heap optimal solution with reasoning.Step 5: Code the optimal approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Explain: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to identify the right data structure (heap), normalize input, and optimize search space while maintaining correctness.

Common Follow-ups

• What if we could only halve elements? → Explain impact on solution
• How to handle very large inputs efficiently? → Discuss heap and complexity

💡 These follow-ups test your understanding of problem constraints and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves minimizing range or deviation; 2) Allowed operations transform elements conditionally; 3) Need to track min and max dynamically; 4) Constraints require efficient data structure like heap.

Signature Phrases

minimum possible deviationif even, divide by 2if odd, multiply by 2

NOT This Pattern When

Problems that only require sorting or simple greedy without dynamic min/max tracking

Similar Problems

Sliding Window Maximum - uses heaps to track max/min in a windowSmallest Range Covering Elements from K Lists - uses heaps to minimize rangeFind K-th Smallest Pair Distance - uses sorting and two pointers for range optimization

Practice

1. Given the following code snippet and inputs, what is the final returned value of W after executing findMaxCapital(2, 0, [1, 2, 3], [0, 1, 1])?

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Trace first iteration with W=0

   Projects with capital ≤0: only (0,1). Move profit 1 to max heap. Pop max profit 1, W=0+1=1.

2. Step 2: Trace second iteration with W=1

   Projects with capital ≤1: (1,2) and (1,3). Move profits 2 and 3 to max heap. Pop max profit 3, W=1+3=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final capital after 2 projects is 4 [OK]

Hint: Track heap contents and W updates carefully [OK]

Common Mistakes:

• Forgetting to push all affordable projects each iteration
• Off-by-one error in loop iterations
• Confusing min-heap and max-heap usage

2. You are given a sequence of tasks represented by integers, and a cooldown period space. Each task must be scheduled on a day such that the same task does not occur again until after space days have passed. Which algorithmic approach guarantees the minimum total days to complete all tasks while respecting the cooldown constraint?

easy

A. Greedy scheduling by always picking the next available task without tracking cooldowns explicitly

B. Simulating each day and checking all tasks to find the earliest valid task to schedule

C. Tracking the next available day for each task using a hash map and scheduling tasks greedily based on that

D. Dynamic programming with a 2D table representing tasks and days to find the minimum schedule length

Solution

1. Step 1: Understand the cooldown constraint

   Each task cannot be scheduled again until space days have passed since its last execution.

2. Step 2: Identify the approach that efficiently tracks cooldowns

   Using a hash map to record the next available day for each task allows scheduling tasks greedily without simulating every day explicitly, ensuring minimal total days.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map tracks cooldowns efficiently -> [OK]

Hint: Track next available day per task with a hash map [OK]

Common Mistakes:

• Assuming greedy without cooldown tracking always works
• Using DP which is unnecessary and inefficient here
• Simulating day-by-day leading to TLE

3. What is the time complexity of adding a number and finding the median using the balanced two heaps approach (max-heap and min-heap) for a data stream of size n?

medium

A. O(n) per addNum and O(1) per findMedian

B. O(log n) per addNum and O(log n) per findMedian

C. O(1) per addNum and O(1) per findMedian

D. O(log n) per addNum and O(1) per findMedian

Solution

1. Step 1: Analyze addNum complexity

   Adding a number involves pushing into one heap and possibly balancing heaps, each heap operation is O(log n).

2. Step 2: Analyze findMedian complexity

   Median is retrieved from the top elements of heaps without modification, so O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap insertions are O(log n), median peek is O(1) -> [OK]

Hint: Heap insertions cost O(log n), median peek is O(1) [OK]

Common Mistakes:

• Assuming findMedian requires sorting or heap operations
• Confusing addNum as O(n) due to balancing
• Thinking addNum is O(1) ignoring heap operations

4. What is the time complexity of the optimal algorithm that sorts engineers by efficiency and uses a min-heap to maintain speeds when selecting a team of size at most k from n engineers?

medium

A. O(n log n) due to sorting and heap operations on at most k elements

B. O(n^2) because for each engineer we might compare with all others in the heap

C. O(n * k) because each engineer is processed and heap operations take O(k)

D. O(k log n) since heap operations dominate and depend on n

Solution

1. Step 1: Identify sorting cost

   Sorting n engineers by efficiency takes O(n log n).

2. Step 2: Analyze heap operations

   Each engineer is pushed into a min-heap of size at most k, so each push/pop is O(log k). Since k ≤ n, heap operations total O(n log k).

3. Step 3: Combine complexities

   Total time is O(n log n + n log k). Since k ≤ n, this simplifies to O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting dominates, heap operations are logarithmic in k [OK]

Hint: Sorting dominates; heap ops are O(log k) per element [OK]

Common Mistakes:

• Confusing heap size with n
• Assuming heap ops are O(k) not O(log k)
• Ignoring sorting cost

5. Suppose the sliding window median problem is modified so that elements can be reused multiple times in different windows (i.e., the input array contains many repeated values). Which modification to the balanced two heaps approach is necessary to maintain correct median calculation efficiently?

hard

A. Use a simple array and sort each window since duplicates simplify median calculation.

B. Replace heaps with a balanced BST or TreeMap to support efficient duplicate counts and removals.

C. Ignore duplicates and treat all elements as unique to simplify heap operations.

D. Use a single max-heap only, as duplicates do not affect median calculation.

Solution

1. Step 1: Understand duplicate handling challenges

   Heaps do not support efficient removal of arbitrary duplicates; lazy deletion becomes complex.

2. Step 2: Use balanced BST or TreeMap

   Balanced BST structures support counting duplicates and efficient insertion/removal, maintaining order for median retrieval.

3. Step 3: Evaluate other options

   Sorting each window is inefficient; ignoring duplicates breaks correctness; single heap cannot maintain median.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Balanced BST handles duplicates efficiently for sliding window median [OK]

Hint: Balanced BST supports duplicates and efficient removals [OK]

Common Mistakes:

• Assuming duplicates simplify median calculation
• Ignoring complexity of removing duplicates from heaps
• Using single heap for median