Part 1 — Beginner Level (Problems 0–10)
Sorting is one of the core foundations of Data Structures and Algorithms. Many interview questions become easier after sorting the data.
Problem 0 — Sort Three Numbers
Difficulty
Easy
Problem Statement
You are given three integers a, b, and c.
Your task is to return the numbers in ascending order.
The result should be returned as an array or list.
Input
Three integers.
a = 7
b = 2
c = 5
Output
[2,5,7]
Example 1
Input
a = 10
b = 3
c = 6
Output
[3,6,10]
Explanation
The numbers sorted in ascending order are:
3 < 6 < 10
Constraints
-10^6 ≤ a,b,c ≤ 10^6
Hint
You can solve this by:
- comparing numbers manually
- using a small sorting algorithm
- using built-in sort function
Problem 1 — Sort an Integer Array
Difficulty
Easy
Problem Statement
Given an integer array nums, sort the array in ascending order and return it.
You may use any sorting algorithm such as:
- Bubble Sort
- Merge Sort
- Quick Sort
- Heap Sort
Input
nums = [5,2,3,1]
Output
[1,2,3,5]
Example 2
Input
nums = [5,1,1,2,0,0]
Output
[0,0,1,1,2,5]
Constraints
1 ≤ nums.length ≤ 50000
-50000 ≤ nums[i] ≤ 50000
Explanation
Sorting the numbers in ascending order means:
smallest → largest
Original:
5,2,3,1
Sorted:
1,2,3,5
Hint
Efficient algorithms:
Merge Sort → O(n log n)
Quick Sort → O(n log n)
Problem 2 — Sort Array in Descending Order
Difficulty
Easy
Problem Statement
Given an array of integers nums, sort the array in descending order.
Input
nums = [1,5,3,2]
Output
[5,3,2,1]
Example 2
Input
nums = [10,4,7,1]
Output
[10,7,4,1]
Explanation
Descending order means:
largest → smallest
Constraints
1 ≤ nums.length ≤ 10^5
Hint
You can:
- sort normally
- reverse the result
Problem 3 — Check if Array is Sorted
Difficulty
Easy
Problem Statement
Given an array nums, determine whether the array is sorted in non-decreasing order.
Return:
true → if sorted
false → otherwise
Input
nums = [1,2,3,4,5]
Output
true
Example 2
Input
nums = [1,3,2]
Output
false
Explanation
The second example fails because:
3 > 2
So the array is not sorted.
Constraints
1 ≤ nums.length ≤ 10^5
Hint
Loop through the array and check:
nums[i] ≤ nums[i+1]
Problem 4 — Bubble Sort Implementation
Difficulty
Easy
Problem Statement
Implement the Bubble Sort algorithm to sort an array in ascending order.
Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
Input
nums = [5,1,4,2]
Output
[1,2,4,5]
Example
Original array
5 1 4 2
Pass 1
1 5 4 2
1 4 5 2
1 4 2 5
Pass 2
1 4 2 5
1 2 4 5
Sorted array
1 2 4 5
Constraints
1 ≤ nums.length ≤ 1000
Time Complexity
O(n²)
Problem 5 — Selection Sort Implementation
Difficulty
Easy
Problem Statement
Implement Selection Sort to sort the array.
Selection Sort works by repeatedly selecting the minimum element from the unsorted part and placing it at the beginning.
Input
nums = [64,25,12,22,11]
Output
[11,12,22,25,64]
Explanation
Steps
11 25 12 22 64
11 12 25 22 64
11 12 22 25 64
Time Complexity
O(n²)
Problem 6 — Insertion Sort Implementation
Difficulty
Easy
Problem Statement
Sort the array using Insertion Sort.
Insertion sort builds the sorted array one element at a time.
Input
nums = [8,3,5,2]
Output
[2,3,5,8]
Explanation
Steps:
8
3 8
3 5 8
2 3 5 8
Time Complexity
Best Case → O(n)
Worst Case → O(n²)
Problem 7 — Move Zeros to End
Difficulty
Easy
Problem Statement
Given an array nums, move all 0s to the end of the array while maintaining the relative order of non-zero elements.
Input
nums = [0,1,0,3,12]
Output
[1,3,12,0,0]
Explanation
Original
0 1 0 3 12
Move zeros
1 3 12 0 0
Constraints
1 ≤ nums.length ≤ 10^4
Problem 8 — Sort Even and Odd Numbers
Difficulty
Easy
Problem Statement
Rearrange the array so that:
All even numbers appear first
All odd numbers appear after them
The relative order does not matter.
Input
nums = [3,1,2,4]
Output
[2,4,3,1]
Explanation
Even numbers
2 4
Odd numbers
3 1
Combined
2 4 3 1
Problem 9 — Sort 0s and 1s
Difficulty
Easy
Problem Statement
Given a binary array containing only 0 and 1, sort the array.
Input
nums = [1,0,1,0,1]
Output
[0,0,1,1,1]
Hint
Count number of:
zeros
ones
Problem 10 — Sort Array by Absolute Value
Difficulty
Easy
Problem Statement
Sort the array based on the absolute value of numbers.
Input
nums = [-4,-1,0,3,10]
Output
[0,-1,3,-4,10]
Explanation
Absolute values:
0 → 0
-1 → 1
3 → 3
-4 → 4
10 → 10
Sorted by absolute value.
Part 2 — Intermediate Level (Problems 11–20)
These problems introduce real interview patterns where sorting is used with:
- Two pointers
- Hash maps
- Custom comparators
- Frequency counting
- Merging sorted data
Problem 11 — Sort Colors (Dutch National Flag Problem)
Difficulty: Medium
Problem Statement
You are given an array nums containing n objects colored red, white, or blue, represented by the integers:
0 → red
1 → white
2 → blue
Sort the array in-place so that objects of the same color are adjacent in the order:
0 → 1 → 2
You must solve the problem without using the built-in sort function.
Input
nums = [2,0,2,1,1,0]
Output
[0,0,1,1,2,2]
Example 2
Input
nums = [2,0,1]
Output
[0,1,2]
Constraints
1 ≤ nums.length ≤ 300
nums[i] ∈ {0,1,2}
Explanation
The sorted order should be:
0s → first
1s → middle
2s → last
Hint
Use the Dutch National Flag Algorithm with three pointers:
low
mid
high
Time Complexity:
O(n)
Problem 12 — Merge Two Sorted Arrays
Difficulty: Easy
Problem Statement
You are given two sorted arrays nums1 and nums2.
Merge nums2 into nums1 as one sorted array.
Input
nums1 = [1,2,3]
nums2 = [2,5,6]
Output
[1,2,2,3,5,6]
Example 2
Input
nums1 = [1,3,5]
nums2 = [2,4,6]
Output
[1,2,3,4,5,6]
Constraints
1 ≤ nums1.length, nums2.length ≤ 1000
Explanation
Because both arrays are already sorted, we can merge them similar to the Merge step in Merge Sort.
Hint
Use two pointers:
i → nums1
j → nums2
Compare elements and insert the smaller one.
Problem 13 — Intersection of Two Sorted Arrays
Difficulty: Easy
Problem Statement
Given two sorted arrays, return their intersection.
The intersection should contain common elements appearing in both arrays.
Input
nums1 = [1,2,2,3]
nums2 = [2,2]
Output
[2,2]
Example 2
Input
nums1 = [1,3,4,5]
nums2 = [2,3,5,7]
Output
[3,5]
Constraints
1 ≤ nums1.length, nums2.length ≤ 1000
Hint
Use two pointers to scan both arrays.
Problem 14 — Union of Two Sorted Arrays
Difficulty: Easy
Problem Statement
Given two sorted arrays, return the union of the arrays.
The union should contain all unique elements from both arrays.
Input
nums1 = [1,2,4]
nums2 = [2,3,5]
Output
[1,2,3,4,5]
Example 2
Input
nums1 = [1,1,2,3]
nums2 = [2,3,4]
Output
[1,2,3,4]
Hint
Use:
two pointers
set
Problem 15 — Sort Array by Frequency
Difficulty: Medium
Problem Statement
Given an integer array nums, sort the array based on the frequency of values.
Rules:
- Numbers with lower frequency come first
- If frequencies are equal, larger numbers appear first
Input
nums = [2,3,1,3,2]
Output
[1,3,3,2,2]
Explanation
Frequencies:
1 → 1 time
3 → 2 times
2 → 2 times
Because 3 and 2 appear the same number of times, the larger number comes first.
Hint
Steps:
- Count frequencies using a hashmap
- Sort using a custom comparator
Problem 16 — Relative Sort Array
Difficulty: Medium
Problem Statement
You are given two arrays:
arr1
arr2
Elements in arr2 are unique and appear in arr1.
Sort arr1 such that:
- Elements in
arr2appear first - Their order matches
arr2 - Remaining elements appear in ascending order
Input
arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]
Output
[2,2,2,1,4,3,3,9,6,7,19]
Hint
Use:
HashMap + Sorting
Problem 17 — Sort Characters by Frequency
Difficulty: Medium
Problem Statement
Given a string s, sort it in descending order based on character frequency.
Input
s = "tree"
Output
"eert"
Explanation
Frequency:
e → 2
t → 1
r → 1
The result starts with the most frequent character.
Hint
Steps:
count frequency
sort by frequency
rebuild string
Problem 18 — Sort Matrix Diagonally
Difficulty: Medium
Problem Statement
Given a matrix mat, sort each diagonal in ascending order.
Input
mat =
[
[3,3,1],
[2,2,1],
[1,1,1]
]
Output
[
[1,1,1],
[1,2,2],
[1,2,3]
]
Explanation
Each diagonal must be sorted independently.
Hint
Use:
HashMap<diagonal, values>
Then sort each list.
Problem 19 — Sort Linked List
Difficulty: Medium
Problem Statement
Given the head of a linked list, sort it in ascending order.
Input
4 → 2 → 1 → 3
Output
1 → 2 → 3 → 4
Constraints
0 ≤ nodes ≤ 50,000
Hint
Best solution:
Merge Sort on Linked List
Time Complexity:
O(n log n)
Problem 20 — Sort People by Height
Difficulty: Easy
Problem Statement
You are given two arrays:
names
heights
Sort the people by heights in descending order and return the names.
Input
names = ["Mary","John","Emma"]
heights = [180,165,170]
Output
["Mary","Emma","John"]
Explanation
Sorted by height:
180 → Mary
170 → Emma
165 → John
Great — let’s continue the series.
Below is Part 3: Problems 21–30 in a LeetCode-style detailed format, moving toward advanced sorting patterns such as QuickSelect, inversion counting, and swap optimization.
Part 3 — Upper-Intermediate Level (Problems 21–30)
These problems combine sorting with algorithmic techniques like:
- Greedy strategies
- Divide and conquer
- QuickSelect
- Heap / priority queue
- Mathematical observations
These appear frequently in coding interviews.
Problem 21 — Kth Largest Element in an Array
Difficulty: Medium
Problem Statement
Given an integer array nums and an integer k, return the kth largest element in the array.
Note:
The kth largest element is the element that would appear in position k if the array were sorted in descending order.
Input
nums = [3,2,1,5,6,4]
k = 2
Output
5
Example 2
Input
nums = [3,2,3,1,2,4,5,5,6]
k = 4
Output
4
Constraints
1 ≤ k ≤ nums.length ≤ 100000
-10^4 ≤ nums[i] ≤ 10^4
Explanation
Sorted descending:
[6,5,4,3,2,1]
2nd largest element = 5
Hint
Efficient solutions:
QuickSelect
Heap
Time Complexity:
Average → O(n)
Problem 22 — Kth Smallest Element in an Array
Difficulty: Medium
Problem Statement
Given an array nums and an integer k, return the kth smallest element.
Input
nums = [7,10,4,3,20,15]
k = 3
Output
7
Explanation
Sorted array:
[3,4,7,10,15,20]
3rd smallest = 7
Hint
Use:
QuickSelect
Min Heap
Sorting
Problem 23 — Minimum Swaps to Sort Array
Difficulty: Medium
Problem Statement
Given an array of distinct integers, determine the minimum number of swaps required to sort the array.
Input
nums = [4,3,2,1]
Output
2
Explanation
Initial:
4 3 2 1
Swap:
4 ↔ 1
3 ↔ 2
Sorted:
1 2 3 4
Total swaps = 2
Hint
Use cycle detection in permutation.
Time Complexity:
O(n log n)
Problem 24 — Count Inversions in Array
Difficulty: Medium
Problem Statement
An inversion occurs when:
i < j
nums[i] > nums[j]
Your task is to count the total number of inversions in the array.
Input
nums = [2,4,1,3,5]
Output
3
Explanation
Inversions:
(2,1)
(4,1)
(4,3)
Total = 3
Hint
Efficient solution:
Merge Sort modification
Time Complexity:
O(n log n)
Problem 25 — Pancake Sorting
Difficulty: Medium
Problem Statement
You are given an array arr.
In one operation you can flip the first k elements of the array.
Return a sequence of flips that sorts the array.
Input
arr = [3,2,4,1]
Output
[4,2,4,3]
Explanation
Flip operations reverse prefixes until array becomes sorted.
Hint
Idea:
Bring largest element to front
Then flip to its correct position
Problem 26 — Wiggle Sort
Difficulty: Medium
Problem Statement
Reorder the array such that:
nums[0] ≤ nums[1] ≥ nums[2] ≤ nums[3] ≥ nums[4]
Input
nums = [3,5,2,1,6,4]
Output
[3,5,1,6,2,4]
Explanation
Check the pattern:
3 ≤ 5 ≥ 1 ≤ 6 ≥ 2 ≤ 4
Hint
Sort first then rearrange or use single pass swapping.
Problem 27 — Wiggle Sort II
Difficulty: Medium/Hard
Problem Statement
Rearrange numbers so that:
nums[0] < nums[1] > nums[2] < nums[3] > nums[4]
Input
nums = [1,5,1,1,6,4]
Output
[1,6,1,5,1,4]
Hint
Steps:
Find median
Three-way partition
Rearrange
Problem 28 — Maximum Gap
Difficulty: Hard
Problem Statement
Given an integer array nums, find the maximum difference between two successive elements in the sorted form of the array.
You must solve it in linear time.
Input
nums = [3,6,9,1]
Output
3
Explanation
Sorted array:
[1,3,6,9]
Differences:
2,3,3
Maximum = 3
Hint
Use Bucket Sort / Pigeonhole Principle.
Problem 29 — Top K Frequent Elements
Difficulty: Medium
Problem Statement
Given an integer array nums and an integer k, return the k most frequent elements.
Input
nums = [1,1,1,2,2,3]
k = 2
Output
[1,2]
Explanation
Frequency:
1 → 3 times
2 → 2 times
3 → 1 time
Top 2 frequent elements:
1,2
Hint
Possible approaches:
Heap
Bucket Sort
QuickSelect
Problem 30 — Sort Nearly Sorted Array
Difficulty: Medium
Problem Statement
An array is k-sorted if every element is at most k positions away from its sorted position.
Sort the array efficiently.
Input
nums = [6,5,3,2,8,10,9]
k = 3
Output
[2,3,5,6,8,9,10]
Hint
Use a Min Heap of size k+1.
Time Complexity:
O(n log k)
Below is Part 4 of the Sorting DSA Series (LeetCode Style).
These problems move from advanced → interview level and involve Quick Sort ideas, custom sorting, and greedy sorting logic.
🧠 Sorting Problems (Hero Level) — Part 4
16. Maximum Gap
Difficulty: Hard
Concepts: Sorting, Bucket Sort, Pigeonhole Principle
Problem
Given an integer array nums, return the maximum difference between two successive elements in its sorted form.
If the array contains less than two elements, return 0.
You must solve it in linear time and space if possible.
Example 1
Input:
nums = [3,6,9,1]
Output:
3
Explanation
Sorted array:
[1,3,6,9]
Differences:
3-1 = 2
6-3 = 3
9-6 = 3
Maximum gap = 3
Example 2
Input:
nums = [10]
Output:
0
Explanation
Only one element → no gap exists.
Constraints
1 ≤ nums.length ≤ 10^5
0 ≤ nums[i] ≤ 10^9
Follow-up
Solve in O(n) time without directly sorting.
17. Largest Number
Difficulty: Medium
Concepts: Custom Sorting, Comparator
Problem
Given a list of non-negative integers, arrange them such that they form the largest possible number.
Return the result as a string.
Example 1
Input:
nums = [10,2]
Output:
"210"
Example 2
Input:
nums = [3,30,34,5,9]
Output:
"9534330"
Explanation
Numbers must be sorted based on which concatenation produces a larger number.
Compare:
34 + 3 = 343
3 + 34 = 334
Since 343 > 334, 34 should come before 3.
Constraints
1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 10^9
18. H-Index
Difficulty: Medium
Concepts: Sorting, Counting
Problem
Given an array citations, where citations[i] is the number of citations a researcher received for their i-th paper.
Return the researcher's h-index.
Definition
A scientist has h-index = h if:
-
hpapers have at least h citations each
Example
Input:
citations = [3,0,6,1,5]
Output:
3
Explanation
Sorted:
[0,1,3,5,6]
There are 3 papers with at least 3 citations.
19. Sort Array by Increasing Frequency
Difficulty: Easy
Concepts: Sorting + HashMap
Problem
Given an array of integers nums, sort the array based on:
- Increasing frequency
- If frequency is same → sort by decreasing number
Example
Input:
nums = [1,1,2,2,2,3]
Output:
[3,1,1,2,2,2]
Explanation
Frequency:
1 → 2 times
2 → 3 times
3 → 1 time
Sorted by frequency:
3 → 1 time
1 → 2 times
2 → 3 times
20. Queue Reconstruction by Height
Difficulty: Hard
Concepts: Sorting + Greedy
Problem
You are given an array people where:
people[i] = [hi, ki]
Where:
-
hi= height of person -
ki= number of people in front with height ≥ hi
Reconstruct the queue.
Example
Input:
people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output:
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation
Sort people by:
1️⃣ Height descending
2️⃣ k-value ascending
Then insert them at position k.
21. Minimum Number of Arrows to Burst Balloons
Difficulty: Medium
Concepts: Sorting + Greedy
Problem
You are given balloons represented by intervals:
[xstart, xend]
An arrow shot at position x bursts all balloons where:
xstart ≤ x ≤ xend
Return the minimum arrows needed.
Example
Input:
points = [[10,16],[2,8],[1,6],[7,12]]
Output:
2
Explanation
Burst:
Arrow 1 → [1,6] and [2,8]
Arrow 2 → [7,12] and [10,16]
22. Minimum Platforms (Train Problem)
Difficulty: Medium
Concepts: Sorting + Two Pointers
Problem
Given arrival and departure times of trains, find the minimum number of platforms required so that no train waits.
Example
Arrival:
[900, 940, 950, 1100, 1500, 1800]
Departure:
[910, 1200, 1120, 1130, 1900, 2000]
Output
3
Explanation
At 11:00 AM, three trains are present simultaneously.
23. Sort a Linked List
Difficulty: Medium
Concepts: Merge Sort on Linked List
Problem
Given the head of a linked list, sort the list in ascending order.
Time complexity should be:
O(n log n)
Example
Input:
head = [4,2,1,3]
Output:
[1,2,3,4]
24. Minimum Difference Between Largest and Smallest
Difficulty: Easy
Concepts: Sorting + Sliding Window
Problem
Given an integer array nums and integer k.
Choose k elements such that the difference between maximum and minimum is minimized.
Example
Input:
nums = [9,4,1,7]
k = 2
Output:
2
Explanation
Sorted:
[1,4,7,9]
Minimum difference:
4 - 1 = 3
7 - 4 = 3
9 - 7 = 2
Answer = 2
Top comments (0)