Sorting & Intervals

The first three problems look unrelated until you read their limits. One sorts numbers that only ever fall between 0 and 9. Another splits up to 30 values into two halves of equal size with the sums as close as possible. The third gives k robots contiguous runs of racks so the busiest robot finishes as early as it can. In each one, the constraints rule out the obvious default (quicksort, a subset-sum table, a partition DP) and point to a different algorithm. The last two are interval problems, merging ranges and counting concurrent jobs, and both start with a sort.

So the reasoning counts as much as the code. Start each one with the brute force, work out its cost out loud, and then move to the better version. Say the arithmetic that rules out the default. C(30, 15) is about 155 million ways to choose a half, and a table over sums that reach into the hundreds of millions, negatives included, won't fit in memory.

The NVIDIA angle

Do the arithmetic before you pick the algorithm. Ten possible values means a ten-slot histogram, and fifteen elements a side means 32,768 subsets per half. A time limit that never needs more robots as it grows means you can binary search it. Say the number each limit implies, then name the technique it points to. These problems also connect to GPU work. The robots problem maps onto splitting a model's layers across GPUs in pipeline stages, the balance NVIDIA's Megatron-LM has to strike, and the max-load balance decides how evenly that pipeline stays busy. The counting pass is the per-block histogram inside a GPU radix sort.

Let the limits pick the algorithm

A tiny value range turns sorting into counting. When every value lies in [0, k), the order between two elements never matters, only how often each value occurs. One pass fills k counters and a walk over the counters writes the output, O(n + k) with no comparisons at all, under the O(n log n) floor that binds every comparison sort.

A small n with huge values turns a subset problem into meet in the middle. A dynamic-programming table over reachable sums only works while the sums stay small. When they run into the hundreds of millions and go negative, split the array in half instead. List every subset sum of each half, which is 2^15 per side at the limit, sort one side and binary search it from the other.

A monotone answer turns a minimization into a search. If a budget T is feasible, every larger budget is feasible too, so binary search T between the largest single item and the total and check each guess with one greedy pass. That costs O(n log S), where S is the total, against O(k n^2) for the partition DP. The binary search on the answer lesson in Foundations builds the template from scratch.

def smallest_feasible(lo, hi, feasible):
    while lo < hi:                      # the answer lies in [lo, hi]
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                    # mid works, so try smaller
        else:
            lo = mid + 1                # mid fails, so the answer is larger
    return lo

Asked at NVIDIA

The first three problems, ordered most frequent first. Partition an Array to Minimize the Sum Difference practices meet in the middle, with the brute force and the subset-sum table priced and rejected before you code. Counting Sort practices the histogram on a tiny range and opens into stable sorting and radix sort. Balancing robots across racks practices binary search on the answer with a greedy check, and closes on the partition DP it replaces. Each test case is the function's arguments as a JSON array. Say the limits and what they rule out before you write each one.

1

Partition an Array to Minimize the Sum Difference: Meet in the Middle

HardFrequently asked

Problem

You're given an integer array nums holding 2 * n integers. Split it into two arrays of length n each, so every element lands in exactly one of them, and make the absolute difference between the two arrays' sums as small as possible. Return that minimum difference.

Both arrays must hold exactly n elements. A split with more elements on one side does not count, even when it would balance the sums better. Values can be negative, and the limits match the LeetCode original: 1 <= n <= 15, with every value between -10^7 and 10^7.

Input[3,9,7,3]Output2

Put 3 and 9 in one array and 7 and 3 in the other. The sums are 12 and 10, a gap of 2, and no split of two against two does better.

Input[-36,36]Output72

With n = 1 there is only one split, -36 against 36, so the answer is |-36 - 36| = 72.

Input[2,-1,0,4,-2,-9]Output0

Take 2, 4 and -9 for one array (sum -3) and -1, 0 and -2 for the other (sum -3). Equal sums give a difference of 0.

How this uses the pattern

Layer meet in the middle on top of subset sums. Split the array into two halves of n, list every subset sum of each half grouped by how many elements it uses, and sort the right groups. A left subset of size k with sum a pairs only with the right group of size n - k, where a binary search finds the sum that brings 2(a + b) closest to the total.

Partition an Array to Minimize the Sum Difference: Meet in the Middle

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (8)

Need a hint? (3 available)

The NVIDIA angle

Splitting an array into equal halves with the smallest sum gap has come up as the dynamic programming question in NVIDIA campus intern interviews, one of the few Hards in NVIDIA's mix. Choosing n of 2n elements at the limit means C(30, 15), about 155 million splits. A subset-sum table looks like the fix until you check the range. Values reach ten million and go negative, so a table over every reachable sum runs to billions of cells. Halving the array leaves 32,768 subsets per side, which sort and search in milliseconds. Work out the brute force cost out loud first, and let that arithmetic lead you to meet in the middle.

Take it further

Return the split itself, then spread the search across threads. Store each subset's bitmask beside its sum, so the winning pairing already names which indices form the first array; the right buckets sort on the sum and carry the mask along. The threading half needs no new data structure. The sorted right buckets are read-only, so every left subset is an independent lookup: hand each thread a slice of left masks, keep a per-thread best, and reduce to one minimum at the end. Worked through below.

Show solution & walkthrough

2

Counting Sort: When the Range Is Tiny, Stop Comparing

EasySometimes asked

Problem

You're given an integer array nums and an integer k. Every value in nums lies between 0 and k - 1 inclusive, and k is small, for example k = 10 when the values are single digits. Return the values of nums in non-decreasing order in O(n + k) time, without comparing one element against another.

Duplicates are expected, and every copy comes back, so the output always holds exactly len(nums) values. A value that never appears contributes nothing. An empty nums returns an empty array, and k = 1 means every value is 0.

Input encoding. Each test case passes two arguments, the array and then k. For example: [[3,0,2,3,9,0,1], 10].

Inputnums = [3, 0, 2, 3, 9, 0, 1]k = 10Output[0, 0, 1, 2, 3, 3, 9]

The histogram reads two 0s, one 1, one 2, two 3s and one 9. Writing each value out as many times as it was counted gives the sorted array.

Inputnums = [7, 7, 7]k = 10Output[7, 7, 7]

Only bucket 7 is non-empty, with a count of 3, so the output is three 7s.

Inputnums = []k = 10Output[]

Every bucket stays at zero, so nothing is written.

How this uses the pattern

Build a histogram, then rebuild the array from it. With only k possible values, the order between two elements never matters, only how many times each value occurs. One pass fills a count array of size k, and a walk over the buckets from 0 to k - 1 writes each value out count[v] times.

Counting Sort: When the Range Is Tiny, Stop Comparing

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (8)

Need a hint? (3 available)

The NVIDIA angle

Sorting 100 numbers that all fall between 0 and 9 has opened a 90-minute NVIDIA campus technical interview. Answer quicksort by reflex and you skip the most useful fact in the prompt, the range. Ten possible values means a ten-slot histogram and a single pass over the input, O(n + k) with zero comparisons, under the O(n log n) floor that binds any comparison sort. Say why the others lose, then tie the histogram to the hardware. Ten counters sit in registers or shared memory, so the input streams through once and the output gets written once. Expect a follow-up on stability or on a range as wide as 2^32.

Take it further

Make it stable for records that carry a key, then sort full 32-bit integers. Re-emitting values loses which record was which, so turn the counts into starting offsets with a prefix sum and drop each record into its key's next free slot, reading the input left to right. A count array with 2^32 slots needs 16 GB of counters. Split each key into four bytes instead and run the stable pass once per byte, low byte first, with 256 buckets each time. GPU radix sorts are built on the same per-block histogram and scan. Worked through below.

Show solution & walkthrough

3

Balance the Robots Across the Racks: Split Array Largest Sum

HardSometimes asked

Problem

A warehouse has n storage racks in a row, and capacities[i] is the number of packages on rack i. You have k robots, and a robot moves one package per unit of time. Each robot is assigned one contiguous run of racks (racks [2, 3, 4] or [5, 6] are fine, racks [1, 3, 4] are not), and every rack belongs to exactly one robot. The robots work in parallel, so the job ends when the busiest robot finishes. Return the smallest possible value of that longest robot time.

Every robot gets at least one rack. When k is larger than the number of racks, or k is 0, no valid assignment exists, so return -1. The capacities arrive sorted in non-decreasing order, though the solution never needs that. (Underneath sits the classic Split Array Largest Sum, with robots standing in for the k subarrays and a -1 rule added.)

Input encoding. Each test passes capacities (a list of non-negative integers, possibly empty) and k. The total package count can pass 2^31, so return the answer as a 64-bit integer.

Inputcapacities = [1,2,3,4,5]k = 2Output9

One robot takes the racks holding 1, 2 and 3 (6 packages) and the other takes 4 and 5 (9 packages). Handing the 4 to the first robot instead pushes it to 10, so 9 is the best you can do.

Inputcapacities = [1,2,3,4,5,6]k = 3Output9

Split as [1,2,3], [4,5], [6] for loads 6, 9 and 6. Any limit below 9 forces 4 and 5 onto separate robots and a fourth robot appears.

Inputcapacities = [4,7]k = 3Output-1

Three robots and two racks leave one robot with no rack at all, which the rules forbid, so no assignment exists.

How this uses the pattern

Binary search on the answer, with a greedy feasibility check. A time limit T is feasible when a left-to-right pass, opening a new robot only when the next rack would push the current one past T, uses at most k robots. Feasibility only improves as T grows, so search between the largest single rack and the total.

Balance the Robots Across the Racks: Split Array Largest Sum

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (12)

Need a hint? (3 available)

The NVIDIA angle

An NVIDIA on-campus intern interview framed this as k warehouse robots clearing racks of packages, each robot owning one contiguous run. Without the warehouse story, it's the linear partition problem, the same balance pipeline parallelism needs. Megatron-LM, NVIDIA's large-model training framework, hands each GPU a contiguous run of transformer layers, and the slowest stage sets the step time for everyone. Minimizing the largest share is that load balance. Reach for binary search on the time limit with a greedy robot count, O(n log S), and be ready to say why it beats the O(k n^2) partition DP. Before coding, ask what the -1 covers, since the original wording leaves open whether a robot may sit idle.

Take it further

Return each robot's run of racks, then write the partition DP the search replaces. The runs come from one more greedy pass at the winning limit, with a forced cut whenever the racks left equal the robots still waiting, so every robot gets a rack. The DP stores, for the first i racks and j robots, the smallest possible maximum, and tries every position for the last cut. It is exact and easy to prove, but it costs O(k n^2), at least 10^10 steps once there are 10^5 racks. Worked through below.

Show solution & walkthrough

Merging and scheduling intervals

Interval problems are a smaller group at NVIDIA, and two cover almost all of them: merging overlapping intervals into the fewest ranges, and counting the most jobs running at the same moment. Both are mediums that start with a sort.

How NVIDIA asks them

NVIDIA asks these in their standard form. Merge Intervals asks for the fewest ranges that cover the same span. The scheduling problem asks for a room count, which you should restate as the most intervals live at any one moment. The follow-ups lean toward cost. You might insert a new interval into an already-merged list, write the heap without the STL, or explain the cache-miss profile of your sweep and how the count would parallelize across many threads.

The NVIDIA angle

Settle the endpoint rule first, then be ready for the performance question. A merge fuses [1,2] and [2,3] because they touch, so the test is start <= prev_end. The room count treats that touch as clean, since a job ending at 2 frees its slot for one starting at 2. Decide which rule applies before you code. Once you've solved it, the interviewer often asks why the O(n) pass beats re-scanning and what keeps the end times in fast cache. They may also ask how it holds up when the schedule is huge.

Sort, then sweep

Both problems start the same way. An interval is a pair, a start and an end, and sorting the intervals by start time makes the rest manageable. Once they're in start order, anything that could overlap an interval sits right next to it, so each one only needs comparing against its neighbors. From there the two problems differ: merging joins neighbors that touch, and the room count tracks how many ranges are live at the same moment.

Three ideas cover both problems. The first is the sort, which lets a single pass from left to right handle the whole set. The second is the overlap test: in sorted order, the current interval overlaps the one you're tracking exactly when its start is less than or equal to that interval's end. In code that is start <= prev_end. If that holds, the two ranges overlap and can be treated as one. If it doesn't, there's a gap between them.

The third idea counts how many ranges are live at once, which is the core of the scheduling problem. A sweep line goes through every start and end in time order with a running tally, adding one when a job begins and subtracting one when it ends, and the peak of that tally is the answer.

A min-heap does the same count a different way. It always gives you its smallest element first. Here it holds the end times of every job currently using a slot, so the top tells you the soonest a slot frees up. Both give the same number, and which one reads more clearly is mostly a matter of taste.

The two problems treat touching endpoints differently, so settle the rule before you write either one. Merging treats touching as overlapping: [1,2] and [2,3] fuse into [1,3], because the test start <= prev_end is true when start equals prev_end. The room-count treats touching as fine: a job that ends at 2 and another that starts at 2 share one slot, because the first has vacated by the instant the second begins. The endpoints are the same in both problems, but the handling is opposite, and NVIDIA interviewers watch whether you read the problem closely enough to pick the right one.

Interval problems

Two problems, ordered the way their difficulty climbs. Merge Intervals practices the sort-then-sweep core and the rule that touching counts as overlap. Meeting Rooms II practices the concurrency count, with both the min-heap and the two-pointer sweep worked through. Work each one in the editor first, then open the walkthrough, saying the endpoint convention out loud as you go, as if an interviewer were watching.

4

Merge Intervals: Sort and Sweep

MediumCommonly asked

Problem

You're given a list intervals where intervals[i] = [start, end]. Merge every set of overlapping intervals and return the fewest intervals that cover exactly the same span, in any order.

Two intervals overlap when they touch or cross, so [1,3] and [2,6] merge into [1,6], and [1,2] and [2,3] merge into [1,3] because they meet at the endpoint.

Inputintervals = [[1,3],[2,6],[8,10],[15,18]]Output[[1,6],[8,10],[15,18]]

[1,3] and [2,6] overlap and merge into [1,6]. The other two touch nothing, so they pass through unchanged.

Inputintervals = [[1,4],[4,5]]Output[[1,5]]

They meet at 4. Touching counts as overlapping here, so they fuse into [1,5].

How this uses the pattern

Sort by start time, then sweep left to right. Keep the last interval in your result open, and for each next interval test start <= prev_end. If it holds, extend the last interval's end to the max of the two; if not, the gap is real, so start a fresh interval.

Merge Intervals: Sort and Sweep

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (6)

Need a hint? (3 available)

The NVIDIA angle

Merge Intervals is the most common interval question in NVIDIA reports, and they ask it as the clean classic. Interviewers check whether you sort first and whether your overlap test counts touching endpoints as overlap, so [1,4] and [4,5] join into one range. They watch for the <= in start <= prev_end. Writing < there is an easy bug to miss, and it leaves touching intervals unmerged.

Take it further

Insert a single new interval into an already-sorted, already-merged list. Since the list is sorted and non-overlapping, you don't re-merge everything. Copy the intervals that end before the new one starts, then absorb every interval that overlaps the new one by widening it, then copy the rest. That is the classic Insert Interval follow-up, and it runs in one linear pass without a sort. Worked through in the walkthrough.

Show solution & walkthrough

5

Concurrent Jobs on a GPU Pool: Meeting Rooms II

MediumSometimes asked

Problem

You're given a list intervals where intervals[i] = [start, end] is a GPU job's start and end time. Return the minimum number of slots a fixed pool needs so that no two jobs sharing a slot ever overlap in time. This is the same as asking the most jobs that ever run at once, which is exactly how many slots the pool must provide. (This is the classic Meeting Rooms II, with rooms standing in for GPU slots.)

A job that ends exactly when another begins, like [1,2] and [2,3], can share one slot: the first has cleared by the instant the second starts.

Inputintervals = [[0,30],[5,10],[15,20]]Output2

[5,10] and [15,20] never overlap each other, but both overlap [0,30], so at the busiest moment two jobs are live and you need two rooms.

Inputintervals = [[7,10],[2,4]]Output1

The two jobs do not overlap at all, so one room hosts both in sequence.

How this uses the pattern

The minimum rooms equals the most jobs live at any single moment. Sort by start. Then either keep a min-heap of the end times of jobs currently in rooms, or sweep the sorted starts and ends together and track the running peak. With the heap, pop any jobs that have ended before the next one starts, then push the new end.

Concurrent Jobs on a GPU Pool: Meeting Rooms II

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (6)

Need a hint? (3 available)

The NVIDIA angle

Meeting Rooms II is the same scheduling pattern, one step harder than a plain merge. It maps directly onto the most jobs that can run at once on a fixed pool of GPUs. Start by restating it: the minimum number of rooms is the most jobs overlapping at one moment. Interviewers look for a min-heap of end times or a sweep in time order instead of a check of every pair. Watch the endpoint rule, since a job ending at the exact time another begins must reuse the slot, so the heap pops when heap[0] <= start and the sweep advances on start < end.

Take it further

Return which jobs collide, or the peak interval where the most rooms are in use. The sweep already exposes this: at the moment the running tally hits its peak, the jobs currently counted are the colliding set. Carry the set of live jobs alongside the tally instead of just a number, and snapshot it when the tally reaches a new high. An interviewer may also ask only whether one machine can run every job in sequence (Meeting Rooms I), which is the same sort plus a single adjacent-overlap check. Worked through below.

Show solution & walkthrough