Find the Duplicate Number in an Array
-
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
An array of n+1 integers contains numbers from 1 to n, with exactly one number repeated. Find that duplicate without modifying the array or using extra space (Floyd's Cycle Detection on indices).
Input: nums = [1, 3, 4, 2, 2]
Output: 2Python Solution
def find_duplicate(nums):
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow2 = nums[0]
while slow != slow2:
slow = nums[slow]
slow2 = nums[slow2]
return slowC++ Solution
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
int slow2 = nums[0];
while (slow != slow2) {
slow = nums[slow];
slow2 = nums[slow2];
}
return slow;
}Java Solution
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
int slow2 = nums[0];
while (slow != slow2) {
slow = nums[slow];
slow2 = nums[slow2];
}
return slow;
}
}Complexity
Time: O(n) treating values as indices forms a cycle, and Floyd's algorithm finds its start in linear time. Space: O(1) only pointer variables are used, no extra array or set.