Minimum Subsequence in Non-Increasing Order

Minimum Subsequence in Non-Increasing Order

What is this problem about?

The Minimum Subsequence in Non-Increasing Order problem asks you to find the smallest subsequence of an array (by length) such that its sum is strictly greater than the sum of the remaining elements. If multiple subsequences have the same minimum length, return the one with the largest sum. This Minimum Subsequence in Non-Increasing Order coding problem is a beginner-friendly greedy problem relying on sorting.

Why is this asked in interviews?

Mercari and Amazon use this as a screening question to verify foundational sorting and greedy skills. It confirms candidates can translate "maximize partial sum with fewest elements" into a simple greedy: take the largest elements first until the condition is satisfied. The array, sorting, and greedy interview pattern is directly applicable.

Algorithmic pattern used

Sort descending, then greedily pick elements from the front. Maintain a running sum of selected elements and the total sum. Keep picking elements until selectedSum > totalSum - selectedSum. The selected elements form the answer subsequence. Return them in non-increasing order (already sorted from step 1).

Example explanation

Array: [4, 3, 10, 9, 8]. Total sum = 34. Sort descending: [10, 9, 8, 4, 3].

• Pick 10: selectedSum = 10. Remaining = 24. 10 > 24? No.
• Pick 9: selectedSum = 19. Remaining = 15. 19 > 15? Yes. Stop. Result: [10, 9].

Common mistakes candidates make

• Sorting in ascending order and picking from the front (opposite direction).
• Not stopping as soon as the condition is satisfied (picking too many elements).
• Returning in the wrong order (must be non-increasing).
• Computing the remaining sum from scratch each time instead of updating it.

Interview preparation tip

Easy greedy problems test code fluency more than algorithmic depth. Practice writing clean, concise solutions: sort, accumulate, stop at condition. The key skill is translating the word problem ("sum strictly greater than remaining") into a precise mathematical condition and implementing it without unnecessary complexity. Getting easy problems right quickly and cleanly is crucial in time-pressured interviews.