Loading…

easyGreedySometimes asked

Permuting Two Arrays

Q: How do you solve Permuting Two Arrays using the Brute Force — Try Every Pairing approach?

When to use it: Mention to show you see the pairing search, then collapse it with the opposite-sort insight. Hold `A` fixed and permute `B` — that explores every possible pairing. For each arrangement, check whether all `A[i] + B[i] >= k`; if any arrangement works, output YES. **Why it's correct.** Permuting one array against a fixed other enumerates all `n!` pairings, so if a feasible pairing exists, this finds it. **Why it's hopeless.** `n!` permutations — even `n = 12` is half a billion. With `n` up to 1000 it never runs. **The structure it reveals.** Among all pairings, the one that gives the *largest possible smallest sum* is small-A-with-large-B. If that arrangement can't clear `k` at every index, no arrangement can; if it can, we're done. So we don't need to try all `n!` — just the opposite-sorted one. Time complexity: O(n! · n). Space complexity: O(n).

Q: How do you solve Permuting Two Arrays using the Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal) approach?

When to use it: The answer they want. Phrase it as 'give the smallest A the biggest B, then verify every pair'. Sort `A` ascending and `B` descending, pair them index-by-index, and check that every `A[i] + B[i] >= k`. If they all do, output YES; otherwise NO. **Why opposite sorting maximises the minimum pair sum — the exchange argument.** Consider any pairing and look at two pairs `(a₁, b₁)` and `(a₂, b₂)` with `a₁ a₁ + b₁` since `b₂ > b₁`, and `a₂ + b₁ > a₁ + b₁` since `a₂ > a₁`. So the swap never lowers the minimum pair sum and can only raise it. Repeatedly applying it sorts A and B into opposite orders — proving that opposite sorting yields the largest achievable minimum pair sum. **Why that settles feasibility.** A feasible permutation exists iff *some* pairing makes the minimum pair sum `≥ k`. Opposite sorting achieves the maximum possible minimum, so if even it falls short at some index, no pairing can succeed (NO); if it clears k everywhere, we have an explicit witness (YES). **Why a single failing index is decisive.** The constraint is universal — every pair must reach k. The opposite-sorted pairing already gives each index the best partner it can get for the min-objective, so one sub-`k` sum here means that element simply cannot be lifted to k by any reordering. Time complexity: O(n log n). Space complexity: O(1).

Greedy Algorithms · 21 of 23 · 8 min

You are given two arrays A and B, each of n integers, and an integer k.

You may permute the elements of both arrays in any order. Determine whether there exists a permutation such that for every index i, A[i] + B[i] >= k.

Return "YES" if such a permutation exists, otherwise "NO".

In plain English

Because both arrays can be reordered, the problem is purely about how we pair their elements. We want every pair to reach k, so we worry most about the pairs likely to fall short. Protecting the small A values by matching them with the large B values gives each weak A the strongest possible partner. If even that arrangement leaves some pair under k, no arrangement can succeed.

Examples

Example 1

Input: A = [2, 1, 3], B = [7, 8, 9], k = 10
Output: YES
Note: Sort A asc [1,2,3], B desc [9,8,7]. Sums 1+9=10, 2+8=10, 3+7=10 — all ≥ 10 → YES.

Example 2

Input: A = [1, 2, 2, 1], B = [3, 3, 3, 4], k = 5
Output: NO
Note: Sort A asc [1,1,2,2], B desc [4,3,3,3]. Sums 1+4=5, 1+3=4 < 5 → fails at index 1 → NO.

Example 3

Input: A = [1, 1, 1], B = [1, 1, 1], k = 3
Output: NO
Note: Every pair sums to 2 < 3 regardless of pairing → NO.

Constraints

1 ≤ n ≤ 1000
1 ≤ k ≤ 10⁹
1 ≤ A[i], B[i] ≤ 10⁹
Both arrays have the same length n

Clarifying questions4First question: Can I permute both arrays, or just one?Explore questions

Q1.Can I permute both arrays, or just one?
Both, independently. So only the pairing of A-elements to B-elements matters, not the original positions.
Q2.Does the threshold apply to each pair or to the total?
To each pair: every index must satisfy A[i] + B[i] >= k. One failing pair makes the answer NO.
Q3.Do the arrays have the same length?
Yes, both are length n, and every A element pairs with exactly one B element.
Q4.Why pair small A with large B?
The smallest A is the hardest to lift over k, so it deserves the largest B. This maximises the minimum pair sum.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You may permute both arrays freely; you need a pairing where every `A[i] + B[i] >= k`. The hardest pair to satisfy is the smallest A paired with the smallest B, so protect the small A values by giving them the largest B values. Sort A ascending and B descending, then check every index: if all `A[i] + B[i] >= k` it's possible ('YES'), otherwise no pairing works ('NO'). O(n log n) from the sorts.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise both arrays are free to permute, and that pairing smallest-with-largest maximises the weakest pair sum — then a single linear feasibility check decides YES/NO.

Where candidates slip

Sorting both arrays the same direction (smallest with smallest, which minimises the worst pair), or trying to brute-force permutations.

How to stand out

Prove via exchange/rearrangement: if a small A is paired with a small B while a large A has a large B, swapping the B's never lowers the minimum pair sum — so opposite sorting is optimal for the min-objective.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Pairing	`O(n! · n)`	`O(n)`	Mention to show you see the pairing search, then collapse it with the opposite-sort insight.	Read
2	Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'give the smallest A the biggest B, then verify every pair'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewArrays A, B, threshold kAll A[i] + B[i] >= k?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Pairing

TimeO(n! · n)SpaceO(n)

Mention to show you see the pairing search, then collapse it with the opposite-sort insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Since both arrays can be permuted, fixing A and permuting B covers all pairings. Try every permutation of B against A.

2Hint 2Explore hint

For each permutation, check that all A[i] + B[i] >= k. If any permutation passes, the answer is YES.

3Hint 3Explore hint

There are n! permutations and each check is O(n) → useless beyond tiny n. It exists only to motivate the opposite-sort greedy.

A · Core idea

Hold A fixed and permute B — that explores every possible pairing. For each arrangement, check whether all A[i] + B[i] >= k; if any arrangement works, output YES.

Why it's correct. Permuting one array against a fixed other enumerates all n! pairings, so if a feasible pairing exists, this finds it.

Why it's hopeless. n! permutations — even n = 12 is half a billion. With n up to 1000 it never runs.

The structure it reveals. Among all pairings, the one that gives the largest possible smallest sum is small-A-with-large-B. If that arrangement can't clear k at every index, no arrangement can; if it can, we're done. So we don't need to try all n! — just the opposite-sorted one.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [1, 2, 2, 1], B = [3, 3, 3, 4], k = 5

B = [4,3,3,3]

sums 5,5,5,4 → index 3 fails

Statenot feasible yet

Final resultNO

C · Code with teaching comments

Reference implementation previewpublic String twoArraysBrute(int k, int[] A, int[] B) { Integer[] b = new Integer[B.length]; for (int i = 0; i < B.length; i++) b[i] = B[i]; return permute(A, b, 0, k) ? "YES" : "NO"; }Explore the full code

solution.javaJava

Brute Force — Try Every Pairing — reference

2 teaching notes

1
public String twoArraysBrute(int k, int[] A, int[] B) {
2
    Integer[] b = new Integer[B.length];
3
    for (int i = 0; i < B.length; i++) b[i] = B[i];
4
    return permute(A, b, 0, k) ? "YES" : "NO";
5
}
6
 
7
private boolean permute(int[] A, Integer[] b, int start, int k) {
8
    if (start == b.length) {
9
        // A pairing is feasible only if EVERY pair reaches k.
10
        for (int i = 0; i < A.length; i++) if (A[i] + b[i] < k) return false;
11
        return true;
12
    }
13
    for (int i = start; i < b.length; i++) {
14
        Integer t = b[start]; b[start] = b[i]; b[i] = t;
15
        // Short-circuit: one feasible permutation is enough to answer YES.
16
        if (permute(A, b, start + 1, k)) return true;
17
        t = b[start]; b[start] = b[i]; b[i] = t;
18
    }
19
    return false;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n! · n) timeO(n) spaceOpen the invariant and proofExplore the proof

Feasibility hinges entirely on the pairing that maximises the minimum pair sum. That pairing is opposite-sorted (small A with large B), so one arrangement decides the whole question.

ComplexityO(n! · n) time, O(n) space — Fixing A and permuting B gives n! pairings; verifying each is O(n). The factorial dominates.

E · Edge cases and pitfalls3n! blow-up — only feasible for n ≤ ~10.Explore edge cases

Pitfalls

n! blow-up — only feasible for n ≤ ~10.
Permuting both arrays (redundant) instead of fixing one and permuting the other.
Forgetting that ALL pairs must satisfy the threshold, not just one.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'give the smallest A the biggest B, then verify every pair'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The pair most at risk of falling below k is the smallest A with the smallest B. Don't let that happen — give small A values large B values.

2Hint 2Explore hint

Sort A ascending and B descending, then pair by index: smallest A with largest B, next-smallest with next-largest, and so on.

3Hint 3Explore hint

Scan once: if any A[i] + B[i] < k the answer is NO; if all reach k it's YES. This pairing maximises the minimum pair sum.

A · Core idea

Sort A ascending and B descending, pair them index-by-index, and check that every A[i] + B[i] >= k. If they all do, output YES; otherwise NO.

Why opposite sorting maximises the minimum pair sum — the exchange argument. Consider any pairing and look at two pairs (a₁, b₁) and (a₂, b₂) with a₁ < a₂ but b₁ < b₂ (the smaller A got the smaller B — a 'same-direction' pairing). Their two sums are a₁ + b₁ and a₂ + b₂, whose minimum is a₁ + b₁ (the smallest A with the smallest B). Swap the B values to get (a₁, b₂) and (a₂, b₁). The new minimum of the two sums is min(a₁ + b₂, a₂ + b₁). Both of these are ≥ a₁ + b₁: a₁ + b₂ > a₁ + b₁ since b₂ > b₁, and a₂ + b₁ > a₁ + b₁ since a₂ > a₁. So the swap never lowers the minimum pair sum and can only raise it. Repeatedly applying it sorts A and B into opposite orders — proving that opposite sorting yields the largest achievable minimum pair sum.

Why that settles feasibility. A feasible permutation exists iff some pairing makes the minimum pair sum ≥ k. Opposite sorting achieves the maximum possible minimum, so if even it falls short at some index, no pairing can succeed (NO); if it clears k everywhere, we have an explicit witness (YES).

Why a single failing index is decisive. The constraint is universal — every pair must reach k. The opposite-sorted pairing already gives each index the best partner it can get for the min-objective, so one sub-k sum here means that element simply cannot be lifted to k by any reordering.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [2, 1, 3], B = [7, 8, 9], k = 10

Array state

i=0

1 + 9 = 10 ≥ 10 ✓

i ↓

1+9

[0]

2+8

[1]

3+7

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal) — optimal

4 teaching notes

1
public String twoArrays(int k, int[] A, int[] B) {
2
    int n = A.length;
3
    Integer[] a = new Integer[n];
4
    Integer[] b = new Integer[n];
5
    for (int i = 0; i < n; i++) { a[i] = A[i]; b[i] = B[i]; }
6
    // A ascending — smallest (hardest to lift) values first.
7
    Arrays.sort(a);
8
    // B descending — largest values first, to back the smallest A's.
9
    Arrays.sort(b, Comparator.reverseOrder());
10
    for (int i = 0; i < n; i++) {
11
        // Any failing pair means no permutation works; cast to long to avoid overflow.
12
        if ((long) a[i] + b[i] < k) return "NO";
13
    }
14
    // All pairs cleared k under the optimal pairing → feasible.
15
    return "YES";
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the rearrangement inequality applied to the MINIMUM (not the sum): to maximise the smallest paired value, sort the two sequences oppositely. The reusable kernel — 'make every pair clear a bar' → defend the weakest A with the strongest B, then one linear check decides feasibility.

ComplexityO(n log n) time, O(1) space — Two sorts cost O(n log n) and dominate; the single verification pass is O(n) with only a boolean flag → O(1) extra space.

E · Edge cases and pitfalls6n = 1 — Single pair: YES iff A[0] + B[0] >= k.Explore edge cases

Edge cases handled

n = 1Single pair: YES iff A[0] + B[0] >= k.
all equal, A=[1,1,1], B=[1,1,1], k=3Every pair sums to 2 < 3 → NO regardless of order.
very large values near 10⁹A[i] + B[i] can exceed int range — compute the sum as long.

Pitfalls

Sorting both arrays the same direction (smallest with smallest) — minimises the worst pair, the opposite of what you want.
Returning YES on the first passing pair instead of requiring ALL pairs to pass.
Integer overflow: 10⁹ + 10⁹ exceeds int; sum as long before comparing to k.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String twoArrays(int k, int[] A, int[] B) { int n = A.length; Integer[] a = new Integer[n]; Integer[] b = new Integer[n]; for (int i = 0; i < n; i++) { a[i] = A[i]; b[i] = B[i]; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Same-direction sorting

Pairing smallest A with smallest B minimises the worst pair sum — the opposite of the goal. Sort B descending against A ascending.

Explore the code comparison

Don't write this

A = sorted(A)
B = sorted(B)   # both ascending → small + small
return "YES" if all(a + b >= k for a, b in zip(A, B)) else "NO"

Write this instead

A = sorted(A)
B = sorted(B, reverse=True)
return "YES" if all(a + b >= k for a, b in zip(A, B)) else "NO"

Returning YES too early

The condition is universal — every pair must reach k. Returning YES on the first passing pair ignores later failures.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) {
    if ((long) a[i] + b[i] >= k) return "YES";  // wrong: only one pair checked
}
return "NO";

Write this instead

for (int i = 0; i < n; i++) {
    if ((long) a[i] + b[i] < k) return "NO";
}
return "YES";

Integer overflow on the sum

A[i] and B[i] can each be 10⁹; their int sum overflows. Add as long before comparing to k.

Explore the code comparison

Don't write this

if (a[i] + b[i] < k) return "NO";  // int + int can overflow

Write this instead

if ((long) a[i] + b[i] < k) return "NO";

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy opposite-sort pairing: smallest with largest to maximise the minimum pair sum

Code pattern to memorize

sort A ascending
sort B descending
for i in 0..n-1:
    if A[i] + B[i] < k: return "NO"
return "YES"

Rules to remember

1You may reorder BOTH arrays independently — the only thing that matters is which A pairs with which B.
2Pair the smallest A with the largest B (ascending A against descending B). This maximises the smallest pair sum.
3If even this optimal pairing has any A[i] + B[i] < k, no permutation can satisfy the constraint → 'NO'.
4All n pair sums must reach k; a single failing index sinks the whole answer.
5Both arrays have the same length n; each A element pairs with exactly one B element.

Use this pattern when

Pair two equal-length arrays to satisfy a per-pair threshold on every pair
Maximising the MINIMUM of paired sums (or products) by choosing the pairing
A feasibility (yes/no) question about whether some pairing meets all constraints
Opposite sorting is the natural move (rearrangement inequality, min-side)

Choose another pattern when

You may pick a subset, not pair all elements → selection problem, not full pairing
The threshold applies to the SUM of all pairs, not each pair → totals, sort same direction
Only one array can be permuted with the other fixed → constrained assignment
Pairs interact beyond their own sum → matching / flow

Interview takeaway

To make every pair clear a threshold, defend the weakest links: give the smallest A values the biggest B values. Sort oppositely and check the per-index minimum. If the best pairing fails anywhere, every pairing does — that's the rearrangement-inequality argument for maximising the minimum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternRearrangement-inequality greedy for the MINIMUM: to make every pair clear a threshold, pair the smallest of one array with the largest of the other (opposite sort), which maximises the smallest pair sum. One linear feasibility check then decides YES/NO.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Greedy Florist
Rearrangement inequality on the SUM — sort oppositely to minimise a weighted total.
Beautiful Pairs
Another two-array greedy, solved by counting rather than pairing-by-sort.
Two City Scheduling
Coming soon
Pair/assign by a sorted difference key — greedy assignment under a balance constraint.
Priyanka and Toys
Sorting unlocks a clean linear pass, as the opposite-sort does here.

Same pattern

←

Largest Permutation

Continue · Next problem

Priyanka and Toys

easyGreedySometimes asked

Permuting Two Arrays

Greedy Algorithms · 21 of 23 · 8 min

You are given two arrays A and B, each of n integers, and an integer k.

You may permute the elements of both arrays in any order. Determine whether there exists a permutation such that for every index i, A[i] + B[i] >= k.

Return "YES" if such a permutation exists, otherwise "NO".

In plain English

Examples

Example 1

Input: A = [2, 1, 3], B = [7, 8, 9], k = 10
Output: YES
Note: Sort A asc [1,2,3], B desc [9,8,7]. Sums 1+9=10, 2+8=10, 3+7=10 — all ≥ 10 → YES.

Example 2

Input: A = [1, 2, 2, 1], B = [3, 3, 3, 4], k = 5
Output: NO
Note: Sort A asc [1,1,2,2], B desc [4,3,3,3]. Sums 1+4=5, 1+3=4 < 5 → fails at index 1 → NO.

Example 3

Input: A = [1, 1, 1], B = [1, 1, 1], k = 3
Output: NO
Note: Every pair sums to 2 < 3 regardless of pairing → NO.

Constraints

1 ≤ n ≤ 1000
1 ≤ k ≤ 10⁹
1 ≤ A[i], B[i] ≤ 10⁹
Both arrays have the same length n

Clarifying questions4First question: Can I permute both arrays, or just one?Explore questions

Q1.Can I permute both arrays, or just one?
Both, independently. So only the pairing of A-elements to B-elements matters, not the original positions.
Q2.Does the threshold apply to each pair or to the total?
To each pair: every index must satisfy A[i] + B[i] >= k. One failing pair makes the answer NO.
Q3.Do the arrays have the same length?
Yes, both are length n, and every A element pairs with exactly one B element.
Q4.Why pair small A with large B?
The smallest A is the hardest to lift over k, so it deserves the largest B. This maximises the minimum pair sum.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise both arrays are free to permute, and that pairing smallest-with-largest maximises the weakest pair sum — then a single linear feasibility check decides YES/NO.

Where candidates slip

Sorting both arrays the same direction (smallest with smallest, which minimises the worst pair), or trying to brute-force permutations.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Pairing	`O(n! · n)`	`O(n)`	Mention to show you see the pairing search, then collapse it with the opposite-sort insight.	Read
2	Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal)Optimal	`O(n log n)`	`O(1)`	The answer they want. Phrase it as 'give the smallest A the biggest B, then verify every pair'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Try Every Pairing

TimeO(n! · n)SpaceO(n)

Mention to show you see the pairing search, then collapse it with the opposite-sort insight.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Since both arrays can be permuted, fixing A and permuting B covers all pairings. Try every permutation of B against A.

2Hint 2Explore hint

For each permutation, check that all A[i] + B[i] >= k. If any permutation passes, the answer is YES.

3Hint 3Explore hint

There are n! permutations and each check is O(n) → useless beyond tiny n. It exists only to motivate the opposite-sort greedy.

A · Core idea

Hold A fixed and permute B — that explores every possible pairing. For each arrangement, check whether all A[i] + B[i] >= k; if any arrangement works, output YES.

Why it's correct. Permuting one array against a fixed other enumerates all n! pairings, so if a feasible pairing exists, this finds it.

Why it's hopeless. n! permutations — even n = 12 is half a billion. With n up to 1000 it never runs.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [1, 2, 2, 1], B = [3, 3, 3, 4], k = 5

B = [4,3,3,3]

sums 5,5,5,4 → index 3 fails

Statenot feasible yet

Final resultNO

C · Code with teaching comments

solution.javaJava

Brute Force — Try Every Pairing — reference

2 teaching notes

1
public String twoArraysBrute(int k, int[] A, int[] B) {
2
    Integer[] b = new Integer[B.length];
3
    for (int i = 0; i < B.length; i++) b[i] = B[i];
4
    return permute(A, b, 0, k) ? "YES" : "NO";
5
}
6
 
7
private boolean permute(int[] A, Integer[] b, int start, int k) {
8
    if (start == b.length) {
9
        // A pairing is feasible only if EVERY pair reaches k.
10
        for (int i = 0; i < A.length; i++) if (A[i] + b[i] < k) return false;
11
        return true;
12
    }
13
    for (int i = start; i < b.length; i++) {
14
        Integer t = b[start]; b[start] = b[i]; b[i] = t;
15
        // Short-circuit: one feasible permutation is enough to answer YES.
16
        if (permute(A, b, start + 1, k)) return true;
17
        t = b[start]; b[start] = b[i]; b[i] = t;
18
    }
19
    return false;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n! · n) timeO(n) spaceOpen the invariant and proofExplore the proof

Feasibility hinges entirely on the pairing that maximises the minimum pair sum. That pairing is opposite-sorted (small A with large B), so one arrangement decides the whole question.

ComplexityO(n! · n) time, O(n) space — Fixing A and permuting B gives n! pairings; verifying each is O(n). The factorial dominates.

E · Edge cases and pitfalls3n! blow-up — only feasible for n ≤ ~10.Explore edge cases

Pitfalls

n! blow-up — only feasible for n ≤ ~10.
Permuting both arrays (redundant) instead of fixing one and permuting the other.
Forgetting that ALL pairs must satisfy the threshold, not just one.

03.2

Approach 2 of 2 · Optimal

Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal)

TimeO(n log n)SpaceO(1)

The answer they want. Phrase it as 'give the smallest A the biggest B, then verify every pair'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The pair most at risk of falling below k is the smallest A with the smallest B. Don't let that happen — give small A values large B values.

2Hint 2Explore hint

Sort A ascending and B descending, then pair by index: smallest A with largest B, next-smallest with next-largest, and so on.

3Hint 3Explore hint

Scan once: if any A[i] + B[i] < k the answer is NO; if all reach k it's YES. This pairing maximises the minimum pair sum.

A · Core idea

Sort A ascending and B descending, pair them index-by-index, and check that every A[i] + B[i] >= k. If they all do, output YES; otherwise NO.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

A = [2, 1, 3], B = [7, 8, 9], k = 10

Array state

i=0

1 + 9 = 10 ≥ 10 ✓

i ↓

1+9

[0]

2+8

[1]

3+7

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Greedy — Sort A Ascending, B Descending, Check Every Pair (Optimal) — optimal

4 teaching notes

1
public String twoArrays(int k, int[] A, int[] B) {
2
    int n = A.length;
3
    Integer[] a = new Integer[n];
4
    Integer[] b = new Integer[n];
5
    for (int i = 0; i < n; i++) { a[i] = A[i]; b[i] = B[i]; }
6
    // A ascending — smallest (hardest to lift) values first.
7
    Arrays.sort(a);
8
    // B descending — largest values first, to back the smallest A's.
9
    Arrays.sort(b, Comparator.reverseOrder());
10
    for (int i = 0; i < n; i++) {
11
        // Any failing pair means no permutation works; cast to long to avoid overflow.
12
        if ((long) a[i] + b[i] < k) return "NO";
13
    }
14
    // All pairs cleared k under the optimal pairing → feasible.
15
    return "YES";
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(1) space — Two sorts cost O(n log n) and dominate; the single verification pass is O(n) with only a boolean flag → O(1) extra space.

E · Edge cases and pitfalls6n = 1 — Single pair: YES iff A[0] + B[0] >= k.Explore edge cases

Edge cases handled

n = 1Single pair: YES iff A[0] + B[0] >= k.
all equal, A=[1,1,1], B=[1,1,1], k=3Every pair sums to 2 < 3 → NO regardless of order.
very large values near 10⁹A[i] + B[i] can exceed int range — compute the sum as long.

Pitfalls

Sorting both arrays the same direction (smallest with smallest) — minimises the worst pair, the opposite of what you want.
Returning YES on the first passing pair instead of requiring ALL pairs to pass.
Integer overflow: 10⁹ + 10⁹ exceeds int; sum as long before comparing to k.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Same-direction sorting

Pairing smallest A with smallest B minimises the worst pair sum — the opposite of the goal. Sort B descending against A ascending.

Explore the code comparison

Don't write this

A = sorted(A)
B = sorted(B)   # both ascending → small + small
return "YES" if all(a + b >= k for a, b in zip(A, B)) else "NO"

Write this instead

A = sorted(A)
B = sorted(B, reverse=True)
return "YES" if all(a + b >= k for a, b in zip(A, B)) else "NO"

Returning YES too early

The condition is universal — every pair must reach k. Returning YES on the first passing pair ignores later failures.

Explore the code comparison

Don't write this

for (int i = 0; i < n; i++) {
    if ((long) a[i] + b[i] >= k) return "YES";  // wrong: only one pair checked
}
return "NO";

Write this instead

for (int i = 0; i < n; i++) {
    if ((long) a[i] + b[i] < k) return "NO";
}
return "YES";

Integer overflow on the sum

A[i] and B[i] can each be 10⁹; their int sum overflows. Add as long before comparing to k.

Explore the code comparison

Don't write this

if (a[i] + b[i] < k) return "NO";  // int + int can overflow

Write this instead

if ((long) a[i] + b[i] < k) return "NO";

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy opposite-sort pairing: smallest with largest to maximise the minimum pair sum

Code pattern to memorize

sort A ascending
sort B descending
for i in 0..n-1:
    if A[i] + B[i] < k: return "NO"
return "YES"

Rules to remember

1You may reorder BOTH arrays independently — the only thing that matters is which A pairs with which B.
2Pair the smallest A with the largest B (ascending A against descending B). This maximises the smallest pair sum.
3If even this optimal pairing has any A[i] + B[i] < k, no permutation can satisfy the constraint → 'NO'.
4All n pair sums must reach k; a single failing index sinks the whole answer.
5Both arrays have the same length n; each A element pairs with exactly one B element.

Use this pattern when

Pair two equal-length arrays to satisfy a per-pair threshold on every pair
Maximising the MINIMUM of paired sums (or products) by choosing the pairing
A feasibility (yes/no) question about whether some pairing meets all constraints
Opposite sorting is the natural move (rearrangement inequality, min-side)

Choose another pattern when

You may pick a subset, not pair all elements → selection problem, not full pairing
The threshold applies to the SUM of all pairs, not each pair → totals, sort same direction
Only one array can be permuted with the other fixed → constrained assignment
Pairs interact beyond their own sum → matching / flow

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Greedy Florist
Rearrangement inequality on the SUM — sort oppositely to minimise a weighted total.
Beautiful Pairs
Another two-array greedy, solved by counting rather than pairing-by-sort.
Two City Scheduling
Coming soon
Pair/assign by a sorted difference key — greedy assignment under a balance constraint.
Priyanka and Toys
Sorting unlocks a clean linear pass, as the opposite-sort does here.

Same pattern

←

Largest Permutation

Continue · Next problem

Priyanka and Toys