Sort an Array of 0s, 1s and 2s (Dutch National Flag)
-
Arrays
- Find the Largest Element in an Array
- Find the Second Largest Element in an Array
- Reverse an Array In Place
- Check if an Array Is Sorted
- Remove Duplicates from a Sorted Array
- Move Zeroes to the End of an Array
- Rotate an Array by K Positions
- Two Sum
- Maximum Subarray Sum (Kadane's Algorithm)
- Best Time to Buy and Sell Stock
- Sort an Array of 0s, 1s and 2s (Dutch National Flag)
- Find the Missing Number in an Array
- Find the Duplicate Number in an Array
- Union of Two Sorted Arrays
- Intersection of Two Sorted Arrays
- Prefix Sum Array and Range Sum Queries
- Majority Element (Boyer-Moore Voting Algorithm)
- Merge Overlapping Intervals
- Next Permutation
- Product of Array Except Self
- Subarray Sum Equals K
- Merge Two Sorted Arrays In Place
- Maximum Product Subarray
- 3Sum: Find All Triplets That Sum to Zero
- Trapping Rain Water
- Container With Most Water
- Rotate Image (Matrix 90 Degree Rotation)
- Spiral Matrix Traversal
- Set Matrix Zeroes
- Kth Largest Element in an Array (Quickselect)
-
Strings
- Reverse a String In Place
- Check if a String Is a Palindrome
- Check if Two Strings Are Anagrams
- Count Frequency of Characters in a String
- First Non-Repeating Character in a String
- Reverse Words in a Sentence
- Check if a String Contains Only Digits
- Remove Duplicate Characters from a String
- Longest Substring Without Repeating Characters
- Group Anagrams
- Valid Parentheses
- String to Integer (atoi)
- Longest Common Prefix
- Implement strStr() - Naive Pattern Matching
- Run-Length Encoding of a String
- Check if a String Is a Rotation of Another
- Longest Palindromic Substring
- Minimum Window Substring
- Zigzag Conversion
- KMP Pattern Matching Algorithm
- Rabin-Karp Pattern Matching Algorithm
- Z-Algorithm for Pattern Matching
- Longest Palindromic Subsequence
- Edit Distance Between Two Strings
- Word Break Problem
- Decode Ways
- String Compression (In-Place)
- Count and Say
- Roman to Integer
- Integer to Roman
- Valid Palindrome II (At Most One Deletion)
- Longest Repeating Character Replacement
- Multiply Two Numbers Represented as Strings
- Why Strings Are Immutable (Interview Concept)
- Time Complexity of Common String Operations (Interview Co...
-
Sliding Window
- Maximum Sum Subarray of Size K (Fixed Window)
- Average of All Subarrays of Size K
- Maximum Number of Vowels in a Substring of Length K
- First Negative Integer in Every Window of Size K
- K Radius Subarray Averages
- Max Consecutive Ones
- Max Consecutive Ones III (At Most K Flips)
- Longest Subarray With Sum At Most K
- Minimum Size Subarray Sum
- Fruit Into Baskets (Longest Subarray With At Most 2 Disti...
- Longest Subarray With At Most K Distinct Elements
- Subarray Product Less Than K
- Maximum Average Subarray I
- Sliding Window Maximum (Monotonic Deque)
- Find All Anagrams in a String (Sliding Window)
- Repeated DNA Sequences (Fixed Window Hashing)
- Longest Turbulent Subarray
- Maximum Erasure Value (Longest Unique Subarray Sum)
- Longest Continuous Increasing Subsequence
- Grumpy Bookstore Owner
- Maximum Points You Can Obtain from Cards
- Binary Subarrays With Sum (Exactly K Trick)
- Count Number of Nice Subarrays (Exactly K Odd Numbers)
- Continuous Subarray Sum (Multiple of K)
- Minimum Operations to Reduce X to Zero
- Maximum Frequency After K Increments
- Sliding Window Median
- Substring With Concatenation of All Words
- Count Complete Subarrays in an Array
- Number of Subarrays With Bounded Maximum
- Maximum Sum of Distinct Subarrays With Length K
- Shortest Subarray With Sum At Least K (With Negatives)
- Fixed-Size vs Variable-Size Sliding Window (Interview Con...
- When to Use Sliding Window vs Two Pointers (Interview Con...
- Recognizing a Sliding Window Problem (Interview Concept)
-
Two Pointers
- Two Sum II - Input Array Is Sorted
- Valid Palindrome (Two Pointer Check)
- Reverse Vowels of a String
- Remove Element In Place
- Move Zeroes Using Two Pointers
- 3Sum Closest
- 4Sum
- Sort Array By Parity
- Squares of a Sorted Array
- Merge Two Sorted Arrays (Two Pointer)
- Intersection of Two Arrays II
- Backspace String Compare
- Trapping Rain Water (Two Pointer Approach)
- Container With Most Water (Two Pointer Approach)
- Partition Labels
- Sort Colors (Dutch National Flag Two Pointer)
- Remove Duplicates from Sorted Array II
- Linked List Cycle Detection (Fast and Slow Pointers)
- Middle of the Linked List
- Palindrome Linked List Check
- Boats to Save People
- Valid Triangle Number
- Minimum Number of Swaps to Make Sequences Increasing
- Sentence Similarity Using Two Pointers
- Shortest Distance to a Character
- Interleaving String Check
- DNA Complement Matching
- Is Subsequence Check (Two Pointer)
- Interview Concept: Same Direction vs Opposite Direction Two Pointers
- Interview Concept: Fast and Slow Pointer Technique Explained
-
Searching & Binary Search
- Binary Search (Classic Iterative)
- Binary Search (Recursive)
- Search Insert Position
- First and Last Position of Element in Sorted Array
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II (With Duplicates)
- Find Minimum in Rotated Sorted Array
- Find Peak Element
- Sqrt(x) Using Binary Search
- Koko Eating Bananas
- Capacity To Ship Packages Within D Days
- Split Array Largest Sum
- Median of Two Sorted Arrays
- Search a 2D Matrix
- Search a 2D Matrix II
- Find K Closest Elements
- Kth Smallest Element in a Sorted Matrix
- Aggressive Cows (Binary Search on Answer)
- Allocate Minimum Number of Pages
- Single Element in a Sorted Array
- Find the Smallest Divisor Given a Threshold
- Binary Search on a Function (Ternary Search Alternative)
- Count of Smaller Numbers After Self
- Time Based Key-Value Store
- Guess Number Higher or Lower
- H-Index II
- Find Right Interval
- Random Pick with Weight
- Interview Concept: Lower Bound vs Upper Bound Binary Search
- Interview Concept: Binary Search on Answer Pattern Explained
-
Sorting
- Bubble Sort Implementation
- Selection Sort Implementation
- Insertion Sort Implementation
- Merge Sort Implementation
- Quick Sort Implementation
- Heap Sort Implementation
- Counting Sort Implementation
- Radix Sort Implementation
- Bucket Sort Implementation
- Sort an Array (Built-in vs Custom Comparator)
- Merge Intervals Using Sorting
- Largest Number Formed from an Array
- Custom Sort String
- Sort Characters By Frequency
- Kth Largest Element (Sorting Approach)
- Relative Sort Array
- Wiggle Sort
- Wiggle Sort II
- H-Index (Sorting Approach)
- Meeting Rooms (Can Attend All Meetings)
Problem
Sort an array containing only 0s, 1s and 2s in place, in a single pass (Dutch National Flag algorithm).
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]Python Solution
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return numsC++ Solution
void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums[low++], nums[mid++]);
} else if (nums[mid] == 1) {
mid++;
} else {
swap(nums[mid], nums[high--]);
}
}
}Java Solution
class Solution {
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
int temp = nums[low]; nums[low] = nums[mid]; nums[mid] = temp;
low++; mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
int temp = nums[mid]; nums[mid] = nums[high]; nums[high] = temp;
high--;
}
}
}
}Complexity
Time: O(n) each element is examined once as the mid pointer moves; low and high only ever narrow the range. Space: O(1) sorted entirely in place with three pointers.