Sorting Coding Problems: 156 Questions with Solutions

How sorting works, step by step

1. The smallest difference between two of these 6 numbers could hide in any of the 15 pairs, and checking every pair is O(n²). Sorting first changes that.
2. Sorted, in O(n log n). Now each number's closest partner is right next to it: anything further along is past that neighbour, so it is at least as far away. Only 5 neighbouring pairs are left to check.
3. 4 and 8 are the first neighbours: 8 − 4 = 4, the best so far. The gap is written under the space between them.
4. 8 and 11 differ by 3, smaller than 4, so the best becomes 3.
5. 11 and 19 differ by 8, not below the best 3, which stays. Any pair further apart spans two or more of these gaps, so the smallest gap is the answer.
6. 19 and 27 differ by 8, not below the best 3, which stays.
7. 27 and 33 differ by 6, not below the best 3, which stays.
8. The smallest difference is 3, between 8 and 11. Sorting cost O(n log n) and the scan 5 comparisons, so O(n log n) in all, against 15 checks unsorted.

Sorting study plan

14 of the 156 Sorting problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 142 in the full list below are practice at your own pace. Then move on to Counting Sort.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Contains Duplicate Easy
• Squares of a Sorted Array Easy
• Merge Sorted Array Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Minimum Difference Between Highest and Lowest of K Scores Easy
• 3Sum Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Car Pooling Medium
• Sort Colors Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Merge Intervals Medium
• Non-overlapping Intervals Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Minimum Number of Arrows to Burst Balloons Medium
• Meeting Rooms II Medium

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Find K-th Smallest Pair Distance Hard

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Maximum Running Time of N Computers Hard

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Russian Doll Envelopes Hard

Next topic: Counting Sort

Sorting: the essentials

When to reach for it

The answer would not change if the input were shuffled — the question is about a collection of values, not their positions — and the brute force compares every pair. "Closest", "minimum difference", "assign each … to a …", "merge the overlapping" and "largest arrangement" all point at sorting first. If the output needs original positions, sort indices or (value, index) pairs instead of the values.

The pattern

Sort once, then scan. A custom comparator must define a consistent order: negative, zero or positive, never a bare boolean, with ties broken explicitly when the output must be deterministic. When a key is costly to compute, compute it once per element rather than inside every comparison.

from functools import cmp_to_key

def largest_number(nums):           # a before b when a+b > b+a
    s = [str(n) for n in nums]
    s.sort(key=cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)))
    out = "".join(s)
    return "0" if out[0] == "0" else out

Cost

Comparison sorts take O(n log n), and no comparison sort can do better in the worst case. Library sorts in Python, Java (for objects) and JavaScript are stable; C++'s std::sort is not, so use std::stable_sort when equal keys must keep their order.

Common mistakes

• A comparator written as a - b overflows on large int values in Java or C++; use Integer.compare(a, b).
• JavaScript's default sort() compares as strings, so [10, 9, 1] sorts to [1, 10, 9]; pass (a, b) => a - b.
• An inconsistent comparator such as JavaScript's (a, b) => a > b, which never returns a negative and gives an engine-dependent order.
• Sorting the input in place when a later step needs the original order.

Start with

• Contains Duplicate: equal values end up adjacent.
• Merge Intervals: sort by start, then one sweep.
• Largest Number: a custom comparator decides everything.

All sorting problems

Easy (53)

• Type of Triangle Array, Math
• Delete Greatest Value in Each Row Array, Matrix, Simulation
• Apple Redistribution into Boxes Array, Greedy
• Check if Array is Good Array, Hash Table
• Neither Minimum nor Maximum Array
• Pair With Given Difference Array, Two Pointers
• Two Sum Less Than K Array, Two Pointers
• Split With Minimum Sum Math, Greedy
• Number of Distinct Averages Array, Hash Table, Two Pointers
• Largest Unique Number Hash Table, Array
• Minimum Number Game Array, Simulation
• Sort the People Array, Hash Table
• Wave Array Array
• Rank Transform of an Array Array, Hash Table
• Minimum Sum of Four Digit Number After Splitting Digits Math, Greedy
• Chocolate Distribution Problem Array, Sliding Window
• Minimum Subsequence in Non-Increasing Order Array, Greedy
• Find the Difference Hash Table, String, Bit Manipulation
• Sort Even and Odd Indices Independently Array
• Sort Integers by The Number of 1 Bits Array, Bit Manipulation, Counting
• Maximum Product of Three Numbers Array, Math
• Minimum Absolute Difference Array
• Sort Array by Increasing Frequency Array, Hash Table
• Largest Perimeter Triangle Array, Math, Greedy
• Sort Array By Parity II Array, Two Pointers
• Maximum Units on a Truck Array, Greedy
• Assign Cookies Array, Two Pointers, Greedy
• Matrix Cells in Distance Order Array, Math, Matrix
• The K Weakest Rows in a Matrix Array, Binary Search, Heap
• Count Pairs Whose Sum is Less than Target Array, Two Pointers, Binary Search
• Minimum Number of Moves to Seat Everyone Array, Greedy, Counting Sort
• Maximum Product Difference Between Two Pairs Array, Greedy
• Special Array With X Elements Greater Than or Equal X Array, Binary Search, Counting Sort
• Maximum Product of Two Elements in an Array Array, Heap
• Array Partition Array, Greedy, Counting Sort
• Minimum Difference Between Highest and Lowest of K Scores Array, Sliding Window
• Check If N and Its Double Exist Array, Hash Table, Two Pointers
• Can Make Arithmetic Progression From Sequence Array
• Sorting the Sentence String
• Relative Sort Array Array, Hash Table, Counting Sort
• Height Checker Array, Counting Sort
• Sort Array By Parity Array, Two Pointers
• Longest Harmonious Subsequence Array, Hash Table, Sliding Window
• Third Maximum Number Array
• Set Mismatch Array, Hash Table, Bit Manipulation
• Intersection of Two Arrays II Array, Hash Table, Two Pointers
• Intersection of Two Arrays Array, Hash Table, Two Pointers
• Meeting Rooms Array, Intervals
• Relative Ranks Array, Heap
• Squares of a Sorted Array Array, Two Pointers
• Merge Sorted Array Array, Two Pointers
• Contains Duplicate Array, Hash Table
• Valid Anagram Hash Table, String, Counting

Medium (83)

• Longest Subsequence With Limited Sum Array, Binary Search, Greedy
• Count Ways to Group Overlapping Ranges Array, Math
• Sort Vowels in a String String
• Find the Integer Added to Array II Array, Two Pointers, Enumeration
• Count Days Without Meetings Array
• Find the Value of the Partition Array
• K-th Smallest Prime Fraction Array, Binary Search, Heap (Priority Queue)
• Maximum Subsequence Score Array, Greedy, Heap (Priority Queue)
• Single-Threaded CPU Array, Heap (Priority Queue)
• Most Beautiful Item for Each Query Array, Binary Search
• Maximum Number of Events That Can Be Attended Array, Greedy, Heap (Priority Queue)
• Find the Kth Largest Integer in the Array Array, String, Heap (Priority Queue)
• Maximum Star Sum of a Graph Array, Graph, Greedy
• Minimum Operations to Make Median of Array Equal to K Array, Greedy
• Find the Maximum Number of Marked Indices Array, Two Pointers, Greedy
• Maximum Consecutive Floors Without Special Floors Array, Greedy
• Eliminate Maximum Number of Monsters Array, Greedy
• Minimum Number of Arrows to Burst Balloons Array, Greedy, Intervals
• Successful Pairs of Spells and Potions Array, Binary Search, Two Pointers
• Find Right Interval Array, Binary Search
• Minimize the Maximum Difference of Pairs Array, Binary Search, Greedy
• Magnetic Force Between Two Balls Array, Binary Search, Greedy
• Maximum Beauty of an Array After Applying Operation Array, Sliding Window, Binary Search
• Frequency of the Most Frequent Element Array, Sliding Window, Greedy
• Number of Subsequences That Satisfy the Given Sum Condition Array, Two Pointers, Binary Search
• The k Strongest Values in an Array Array, Two Pointers
• Most Profit Assigning Work Array, Two Pointers, Greedy
• Partition Array Such That Maximum Difference Is K Array, Greedy, Two Pointers
• Sort Transformed Array Array, Two Pointers, Math
• Bag of Tokens Array, Two Pointers, Greedy
• Max Number of K-Sum Pairs Array, Two Pointers, Hash Table
• 4Sum Array, Two Pointers
• Find Players With Zero or One Losses Hash Table, Array, Counting
• Determine if Two Strings Are Close Hash Table, String, Counting
• Smallest String With Swaps Union Find, Hash Table, String
• Check If a String Can Break Another String String, Greedy
• Longest Word in Dictionary Through Deleting String, Two Pointers
• Count Triplets With Sum Smaller Than X Array, Two Pointers
• Kth Smallest Element Array, Quickselect
• Minimum Swaps to Sort Array, Graph
• Divide Array Into Arrays With Max Difference Array, Greedy
• Smallest Value of the Rearranged Number Math
• Find Original Array From Doubled Array Array, Greedy, Hash Table
• Minimum Moves to Equal Array Elements II Array, Math
• Maximum Total Importance of Roads Graph, Greedy, Heap
• The Earliest Moment When Everyone Become Friends Array, Union Find
• Sort Integers by The Power Value Dynamic Programming, Memoization
• The Number of Weak Characters in the Game Array, Greedy, Stack
• Max Chunks To Make Sorted Array, Stack, Greedy
• Reveal Cards In Increasing Order Array, Queue, Simulation
• Minimum Number of Platforms Array, Greedy, Two Pointers
• Find K Closest Elements Array, Two Pointers, Binary Search
• Kth Smallest Element in a Sorted Matrix Array, Binary Search, Heap
• Top K Frequent Words Array, Hash Table, String
• K Closest Points to Origin Array, Math, Divide and Conquer
• Valid Triangle Number Array, Two Pointers, Binary Search
• Maximum Number of Coins You Can Get Array, Math, Greedy
• Largest Number Array, String, Greedy
• Maximum Ice Cream Bars Array, Greedy, Counting Sort
• Remove Covered Intervals Array, Greedy
• Minimum Deletions to Make Character Frequencies Unique String, Hash Table, Greedy
• Reduce Array Size to The Half Array, Hash Table, Greedy
• Queue Reconstruction by Height Array, Greedy, Binary Indexed Tree
• Two City Scheduling Array, Greedy
• Maximum Length of Pair Chain Array, Dynamic Programming, Greedy
• Sort the Matrix Diagonally Array, Matrix
• Custom Sort String Hash Table, String
• Majority Element II Array, Hash Table, Counting
• H-Index Array, Counting Sort
• Shortest Unsorted Continuous Subarray Array, Two Pointers, Monotonic Stack
• 3Sum Closest Array, Two Pointers
• 3Sum Array, Two Pointers
• Car Pooling Array, Prefix Sum, Intervals
• Minimum Number of Arrows to Burst Balloons Array, Greedy, Intervals
• Meeting Rooms II Array, Heap, Intervals
• Non-overlapping Intervals Array, Greedy, Intervals
• Merge Intervals Array, Intervals
• Sort an Array Array, Heap, Divide and Conquer
• Kth Largest Element in an Array Array, Heap, Quickselect
• Boats to Save People Array, Greedy, Two Pointers
• Hand of Straights Array, Greedy, Hash Table
• Car Fleet Array, Stack, Monotonic Stack
• Sort Colors Array, Two Pointers

Hard (20)

• Make Array Strictly Increasing Array, Binary Search, Dynamic Programming
• Maximum Number of Events That Can Be Attended II Array, Binary Search, Dynamic Programming
• Allocate Mailboxes Array, Math, Dynamic Programming
• Maximum Height by Stacking Cuboids Array, Dynamic Programming
• Apply Operations to Maximize Score Array, Math, Stack
• Meeting Rooms III Array, Simulation, Heap (Priority Queue)
• Smallest Range Covering Elements from K Lists Array, Hash Table, Greedy
• Maximum Performance of a Team Array, Greedy, Heap (Priority Queue)
• Put Marbles in Bags Array, Greedy, Heap (Priority Queue)
• Checking Existence of Edge Length Limited Paths Array, Union Find, Graph
• Find All People With Secret Graph, Union Find, Depth-First Search
• Number of Good Paths Array, Tree, Graph
• Minimum Cost to Cut a Stick Array, Dynamic Programming
• Maximum Number of Groups With Increasing Length Array, Greedy, Binary Search
• Minimum Time to Complete All Tasks Array, Greedy
• IPO Array, Greedy, Heap
• Maximum Number of Tasks You Can Assign Array, Binary Search, Greedy
• Russian Doll Envelopes Array, Binary Search, Dynamic Programming
• Maximum Running Time of N Computers Array, Binary Search, Greedy
• Find K-th Smallest Pair Distance Array, Two Pointers, Binary Search

Companies that ask sorting problems

• Amazon 136 problems on sorting
• Google 92 problems on sorting
• Adobe 34 problems on sorting
• Microsoft 24 problems on sorting
• Meta 14 problems on sorting
• TCS 11 problems on sorting
• Bloomberg 10 problems on sorting
• Flipkart 8 problems on sorting
• Infosys 7 problems on sorting
• Uber 7 problems on sorting
• Zoho 4 problems on sorting
• Accenture 3 problems on sorting

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems
• Sliding Window 71 problems