Maximum Gap (Pigeonhole / Sort + Scan)

🎯

Maximum Gap (Pigeonhole / Sort + Scan)

hardSORT_SEARCHAmazonGoogle

Imagine you have a list of timestamps when events occurred, and you want to find the longest idle time between any two consecutive events.

💡 This problem asks for the largest difference between adjacent elements after sorting. Beginners often struggle because the problem seems to require sorting but also hints at a linear time solution using buckets. Understanding why sorting helps and how to avoid sorting the entire array is key.

📋

Problem Statement

Given an unsorted array of integers nums, return the maximum difference between the successive elements in its sorted form. If the array contains less than two elements, return 0.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^9

💡

Example

Input"[3, 6, 9, 1]"

Output3

Sorted array is [1,3,6,9], maximum gap is max(3-1=2,6-3=3,9-6=3) = 3

• Array with one element → output 0
• Array with all elements equal → output 0
• Array with two elements → output difference between them
• Array with large range but few elements → correct bucket sizing

⚠️

Common Mistakes

Not handling arrays with less than two elements

Code may crash or return incorrect result

✅ Add explicit check for array length < 2 and return 0

Incorrect bucket size calculation leading to wrong bucket count

Buckets overlap or miss elements, causing wrong max gap

✅ Use bucket_size = max(1, (max - min) // (n - 1)) and bucket_count accordingly

Assuming max gap is inside a bucket instead of between buckets

Misses the actual maximum gap, returns smaller value

✅ Only consider gaps between buckets, not inside buckets

Sorting numbers as strings in JavaScript

Incorrect order and wrong max gap

✅ Use nums.sort((a,b) => a - b) for numeric sort

Not handling all elements equal case

Returns incorrect max gap instead of 0

✅ Check if min == max and return 0 early

🧠

Brute Force (Sort and Scan)

💡 This approach exists because sorting the array first is the most straightforward way to find adjacent differences. It helps beginners understand the problem by simplifying it to a known operation.

Intuition

Sort the array, then scan through to find the maximum difference between consecutive elements.

Algorithm

1. Sort the input array.
2. Initialize max_gap to 0.
3. Iterate through the sorted array from the second element to the end.
4. Update max_gap with the maximum difference between current and previous element.

💡 The main challenge is realizing that sorting puts elements in order so adjacent differences are meaningful.

</>

Code

from typing import List

def maximumGap(nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    nums.sort()
    max_gap = 0
    for i in range(1, len(nums)):
        max_gap = max(max_gap, nums[i] - nums[i-1])
    return max_gap

# Driver code
if __name__ == '__main__':
    print(maximumGap([3,6,9,1]))  # Output: 3

Line Notes

if len(nums) < 2:Handle edge case where no gap exists

nums.sort()Sort array to bring elements in order

for i in range(1, len(nums)):Scan through sorted array to check adjacent pairs

max_gap = max(max_gap, nums[i] - nums[i-1])Update max_gap with largest difference found

import java.util.*;

public class MaximumGap {
    public static int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        Arrays.sort(nums);
        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) {
            maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
        }
        return maxGap;
    }

    public static void main(String[] args) {
        System.out.println(maximumGap(new int[]{3,6,9,1})); // Output: 3
    }
}

Line Notes

if (nums.length < 2) return 0;Edge case: no gap if less than two elements

Arrays.sort(nums);Sort array to order elements

for (int i = 1; i < nums.length; i++) {Iterate through sorted array

maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);Track maximum adjacent difference

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maximumGap(vector<int>& nums) {
    if (nums.size() < 2) return 0;
    sort(nums.begin(), nums.end());
    int maxGap = 0;
    for (int i = 1; i < nums.size(); i++) {
        maxGap = max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

int main() {
    vector<int> nums = {3,6,9,1};
    cout << maximumGap(nums) << endl; // Output: 3
    return 0;
}

Line Notes

if (nums.size() < 2) return 0;Return 0 if no gap possible

sort(nums.begin(), nums.end());Sort the vector to order elements

for (int i = 1; i < nums.size(); i++) {Loop through sorted elements

maxGap = max(maxGap, nums[i] - nums[i - 1]);Update max gap with adjacent difference

function maximumGap(nums) {
    if (nums.length < 2) return 0;
    nums.sort((a,b) => a - b);
    let maxGap = 0;
    for (let i = 1; i < nums.length; i++) {
        maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

// Test
console.log(maximumGap([3,6,9,1])); // Output: 3

Line Notes

if (nums.length < 2) return 0;Handle arrays too small for gaps

nums.sort((a,b) => a - b);Sort numbers numerically ascending

for (let i = 1; i < nums.length; i++) {Iterate over sorted array

maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);Keep track of largest gap

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting dominates time complexity; scanning is linear. Space depends on sort implementation.

💡 For n=100,000, sorting takes about 1.5 million operations, which is feasible but not optimal.

Interview Verdict: Accepted

This approach works but is not optimal for very large inputs where linear time is desired.

🧠

Bucket Sort / Pigeonhole Principle

💡 This approach exists to achieve linear time by avoiding full sorting. It introduces the pigeonhole principle to distribute numbers into buckets and find max gap between buckets.

Intuition

Divide the range between min and max into buckets so that the maximum gap must be between buckets, not inside them.

Algorithm

1. Find the minimum and maximum values in the array.
2. Calculate bucket size and number of buckets based on the range and array length.
3. Place each number into its corresponding bucket, tracking bucket min and max.
4. Scan buckets to find the maximum gap between the max of one bucket and the min of the next non-empty bucket.

💡 The key insight is that the maximum gap cannot be inside a bucket but only between buckets.

</>

Code

from typing import List

def maximumGap(nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    n = len(nums)
    bucket_size = max(1, (max_num - min_num) // (n - 1))
    bucket_count = (max_num - min_num) // bucket_size + 1
    buckets_min = [float('inf')] * bucket_count
    buckets_max = [float('-inf')] * bucket_count
    for num in nums:
        idx = (num - min_num) // bucket_size
        buckets_min[idx] = min(buckets_min[idx], num)
        buckets_max[idx] = max(buckets_max[idx], num)
    max_gap = 0
    prev_max = buckets_max[0]
    for i in range(1, bucket_count):
        if buckets_min[i] == float('inf'):
            continue
        max_gap = max(max_gap, buckets_min[i] - prev_max)
        prev_max = buckets_max[i]
    return max_gap

# Driver code
if __name__ == '__main__':
    print(maximumGap([3,6,9,1]))  # Output: 3

Line Notes

min_num, max_num = min(nums), max(nums)Find range boundaries

bucket_size = max(1, (max_num - min_num) // (n - 1))Calculate minimum bucket size to ensure max gap between buckets

buckets_min = [float('inf')] * bucket_countInitialize bucket mins to infinity

for num in nums:Place each number in its bucket and update min/max

import java.util.*;

public class MaximumGap {
    public static int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        if (minNum == maxNum) return 0;
        int n = nums.length;
        int bucketSize = Math.max(1, (maxNum - minNum) / (n - 1));
        int bucketCount = (maxNum - minNum) / bucketSize + 1;
        int[] bucketsMin = new int[bucketCount];
        int[] bucketsMax = new int[bucketCount];
        Arrays.fill(bucketsMin, Integer.MAX_VALUE);
        Arrays.fill(bucketsMax, Integer.MIN_VALUE);
        for (int num : nums) {
            int idx = (num - minNum) / bucketSize;
            bucketsMin[idx] = Math.min(bucketsMin[idx], num);
            bucketsMax[idx] = Math.max(bucketsMax[idx], num);
        }
        int maxGap = 0, prevMax = bucketsMax[0];
        for (int i = 1; i < bucketCount; i++) {
            if (bucketsMin[i] == Integer.MAX_VALUE) continue;
            maxGap = Math.max(maxGap, bucketsMin[i] - prevMax);
            prevMax = bucketsMax[i];
        }
        return maxGap;
    }

    public static void main(String[] args) {
        System.out.println(maximumGap(new int[]{3,6,9,1})); // Output: 3
    }
}

Line Notes

int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;Initialize min and max to extremes

int bucketSize = Math.max(1, (maxNum - minNum) / (n - 1));Calculate bucket size to guarantee max gap between buckets

Arrays.fill(bucketsMin, Integer.MAX_VALUE);Initialize bucket mins

for (int num : nums) {Assign numbers to buckets and update min/max

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int maximumGap(vector<int>& nums) {
    if (nums.size() < 2) return 0;
    int minNum = *min_element(nums.begin(), nums.end());
    int maxNum = *max_element(nums.begin(), nums.end());
    if (minNum == maxNum) return 0;
    int n = nums.size();
    int bucketSize = max(1, (maxNum - minNum) / (n - 1));
    int bucketCount = (maxNum - minNum) / bucketSize + 1;
    vector<int> bucketsMin(bucketCount, INT_MAX);
    vector<int> bucketsMax(bucketCount, INT_MIN);
    for (int num : nums) {
        int idx = (num - minNum) / bucketSize;
        bucketsMin[idx] = min(bucketsMin[idx], num);
        bucketsMax[idx] = max(bucketsMax[idx], num);
    }
    int maxGap = 0, prevMax = bucketsMax[0];
    for (int i = 1; i < bucketCount; i++) {
        if (bucketsMin[i] == INT_MAX) continue;
        maxGap = max(maxGap, bucketsMin[i] - prevMax);
        prevMax = bucketsMax[i];
    }
    return maxGap;
}

int main() {
    vector<int> nums = {3,6,9,1};
    cout << maximumGap(nums) << endl; // Output: 3
    return 0;
}

Line Notes

int minNum = *min_element(nums.begin(), nums.end());Find minimum element

int bucketSize = max(1, (maxNum - minNum) / (n - 1));Calculate bucket size to ensure max gap between buckets

vector<int> bucketsMin(bucketCount, INT_MAX);Initialize bucket mins to max int

for (int num : nums) {Assign each number to a bucket and update min/max

function maximumGap(nums) {
    if (nums.length < 2) return 0;
    let minNum = Math.min(...nums);
    let maxNum = Math.max(...nums);
    if (minNum === maxNum) return 0;
    const n = nums.length;
    const bucketSize = Math.max(1, Math.floor((maxNum - minNum) / (n - 1)));
    const bucketCount = Math.floor((maxNum - minNum) / bucketSize) + 1;
    const bucketsMin = new Array(bucketCount).fill(Infinity);
    const bucketsMax = new Array(bucketCount).fill(-Infinity);
    for (const num of nums) {
        const idx = Math.floor((num - minNum) / bucketSize);
        bucketsMin[idx] = Math.min(bucketsMin[idx], num);
        bucketsMax[idx] = Math.max(bucketsMax[idx], num);
    }
    let maxGap = 0, prevMax = bucketsMax[0];
    for (let i = 1; i < bucketCount; i++) {
        if (bucketsMin[i] === Infinity) continue;
        maxGap = Math.max(maxGap, bucketsMin[i] - prevMax);
        prevMax = bucketsMax[i];
    }
    return maxGap;
}

// Test
console.log(maximumGap([3,6,9,1])); // Output: 3

Line Notes

let minNum = Math.min(...nums);Find minimum number in array

const bucketSize = Math.max(1, Math.floor((maxNum - minNum) / (n - 1)));Calculate bucket size to ensure max gap between buckets

const bucketsMin = new Array(bucketCount).fill(Infinity);Initialize bucket mins to Infinity

for (const num of nums) {Place each number into its bucket and update min/max

⏱

Complexity

TimeO(n)

SpaceO(n)

Finding min/max and bucket assignment are linear; scanning buckets is linear too.

💡 For n=100,000, this approach avoids sorting and runs in about 100,000 operations, much faster than sorting.

Interview Verdict: Accepted

This is the optimal approach for large inputs and is preferred in interviews when linear time is required.

🧠

Optimized Sort + Scan with Early Exit

💡 This approach improves the brute force by adding early checks and minor optimizations to reduce overhead, useful when input is nearly sorted or small.

Intuition

Sort and scan as before, but return early if all elements are equal or if array length is small.

Algorithm

1. Check if array length is less than 2, return 0.
2. Find min and max; if equal, return 0 immediately.
3. Sort the array.
4. Scan to find max gap between adjacent elements.

💡 Adding early exits reduces unnecessary work and shows attention to detail.

</>

Code

from typing import List

def maximumGap(nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    nums.sort()
    max_gap = 0
    for i in range(1, len(nums)):
        max_gap = max(max_gap, nums[i] - nums[i-1])
    return max_gap

# Driver code
if __name__ == '__main__':
    print(maximumGap([3,6,9,1]))  # Output: 3

Line Notes

if len(nums) < 2:Handle trivial case with no gap

min_num, max_num = min(nums), max(nums)Check if all elements are equal

if min_num == max_num:Early exit if no gap possible

nums.sort()Sort array to find adjacent differences

import java.util.*;

public class MaximumGap {
    public static int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        int minNum = Integer.MAX_VALUE, maxNum = Integer.MIN_VALUE;
        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }
        if (minNum == maxNum) return 0;
        Arrays.sort(nums);
        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) {
            maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
        }
        return maxGap;
    }

    public static void main(String[] args) {
        System.out.println(maximumGap(new int[]{3,6,9,1})); // Output: 3
    }
}

Line Notes

if (nums.length < 2) return 0;Return 0 if no gap possible

if (minNum == maxNum) return 0;Early exit if all elements equal

Arrays.sort(nums);Sort array for scanning

maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);Track max adjacent gap

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int maximumGap(vector<int>& nums) {
    if (nums.size() < 2) return 0;
    int minNum = *min_element(nums.begin(), nums.end());
    int maxNum = *max_element(nums.begin(), nums.end());
    if (minNum == maxNum) return 0;
    sort(nums.begin(), nums.end());
    int maxGap = 0;
    for (int i = 1; i < nums.size(); i++) {
        maxGap = max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

int main() {
    vector<int> nums = {3,6,9,1};
    cout << maximumGap(nums) << endl; // Output: 3
    return 0;
}

Line Notes

if (nums.size() < 2) return 0;Handle trivial input

if (minNum == maxNum) return 0;Early exit if no gap

sort(nums.begin(), nums.end());Sort array for gap calculation

maxGap = max(maxGap, nums[i] - nums[i - 1]);Update max gap

function maximumGap(nums) {
    if (nums.length < 2) return 0;
    const minNum = Math.min(...nums);
    const maxNum = Math.max(...nums);
    if (minNum === maxNum) return 0;
    nums.sort((a,b) => a - b);
    let maxGap = 0;
    for (let i = 1; i < nums.length; i++) {
        maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

// Test
console.log(maximumGap([3,6,9,1])); // Output: 3

Line Notes

if (nums.length < 2) return 0;Return 0 if array too small

if (minNum === maxNum) return 0;Early exit if all elements equal

nums.sort((a,b) => a - b);Sort array numerically

maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);Track maximum gap

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sort

Same as brute force but with early exits to save time on trivial cases.

💡 Early exits can save time on inputs with no gaps, improving average performance.

Interview Verdict: Accepted

This approach is a minor optimization over brute force and is useful to mention in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the bucket sort approach if asked for optimal; otherwise, brute force is acceptable for initial discussion.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sort and Scan)	O(n log n)	O(1) or O(n)	No	N/A	Mention first, code if time permits
2. Bucket Sort / Pigeonhole Principle	O(n)	O(n)	No	N/A	Optimal approach to code in interviews
3. Optimized Sort + Scan with Early Exit	O(n log n)	O(1) or O(n)	No	N/A	Mention as minor optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify input size and constraints.Step 2: State the brute force approach using sorting and scanning.Step 3: Discuss time complexity and limitations of brute force.Step 4: Introduce the bucket sort / pigeonhole principle approach for linear time.Step 5: Code the optimal approach and test edge cases.Step 6: Mention minor optimizations if time permits.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests understanding of sorting, bucket sort, pigeonhole principle, and ability to optimize time complexity from O(n log n) to O(n).

Common Follow-ups

• What if numbers are floating point? → Use bucket approach with adjusted bucket size.
• Can you do it without sorting? → Yes, bucket sort approach.
• What if input is already sorted? → Early exit or linear scan suffices.
• How to handle duplicates? → They don't affect max gap calculation.

💡 These follow-ups test flexibility and deeper understanding of the problem constraints and solutions.

🔍

Pattern Recognition

When to Use

1) Asked for max difference between adjacent sorted elements; 2) Input is unsorted; 3) Large input size needing optimization; 4) Constraints allow bucket sort.

Signature Phrases

maximum difference between successive elementssorted formmaximum adjacent difference

NOT This Pattern When

This is not a classic DP or sliding window problem despite involving scanning.

Similar Problems

Maximum Consecutive Gap - same concept of max adjacent differenceFind Minimum in Rotated Sorted Array - uses sorting and scanningLongest Consecutive Sequence - related to gaps and sequences

Practice

1. You are given two integer arrays where the first array needs to be sorted such that the relative order of items in the first array follows the order defined by the second array. Elements not present in the second array should be placed at the end in ascending order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by repeatedly selecting the smallest element from the first array that appears in the second array

B. Brute force nested loops checking each element of the first array against the second array

C. Dynamic programming to find the longest subsequence matching the order of the second array

D. Counting sort based on frequency arrays combined with the order defined by the second array

Solution

1. Step 1: Understand problem constraints

   The problem requires sorting the first array so that elements appear in the order defined by the second array, with leftover elements sorted ascending at the end.

2. Step 2: Identify optimal approach

   Counting sort using frequency arrays efficiently counts occurrences and outputs elements in the required order in O(n + k) time, where k is max element value.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Counting sort matches problem constraints and is optimal for integer ranges [OK]

Hint: Frequency counting suits custom order sorting [OK]

Common Mistakes:

• Assuming greedy selection suffices without frequency counting
• Confusing this with subsequence or DP problems
• Using brute force nested loops which is inefficient

2. You are given a sorted array of integers and a quadratic function f(x) = ax² + bx + c. You need to return a sorted array of the values f(x) applied to each element x in the input array. Which approach guarantees an optimal O(n) time solution?

easy

A. Use two pointers at the start and end of the input array and fill the output array from the end or start depending on the sign of a, leveraging the parabola shape.

B. Use dynamic programming to store intermediate results and build the sorted transformed array incrementally.

C. Apply the quadratic function to each element and then sort the resulting array using a standard sorting algorithm.

D. Use a max-heap to insert transformed values and then extract them in sorted order.

Solution

1. Step 1: Understand the parabola shape

   The quadratic function forms a parabola. If a >= 0, the largest values are at the ends of the input array; if a < 0, the smallest values are at the ends.

2. Step 2: Use two pointers to fill output

   By comparing transformed values at both ends, we can fill the output array from the appropriate end in O(n) time without sorting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers leverage sorted input and parabola shape for linear time [OK]

Hint: Two pointers exploit parabola shape for O(n) [OK]

Common Mistakes:

• Assuming sorting is always needed after transformation
• Trying DP without leveraging input order

3. The following code attempts to implement the optimal relative sort array solution. Identify the line containing the subtle bug that causes incorrect output when arr1 contains elements not in arr2.

medium

A. Line 9: Missing resetting freq[val] to zero after processing

B. Line 8: Extending result with elements from arr2 order

C. Line 4: Incrementing frequency count for each num

D. Line 11: Extending result with leftover elements

Solution

1. Step 1: Understand frequency usage

   Frequency array counts occurrences; after outputting elements from arr2, freq[val] must be reset to zero to avoid duplicates.

2. Step 2: Identify missing reset

   Line 9 lacks freq[val] = 0, so leftover loop outputs duplicates of arr2 elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resetting freq[val] prevents duplicate output of arr2 elements [OK]

Hint: Check if frequency counts are zeroed after use [OK]

Common Mistakes:

• Forgetting to reset frequency after outputting arr2 elements
• Misplacing frequency increment or leftover output
• Assuming leftover loop excludes arr2 elements automatically

4. What is the time complexity of the optimal two-pointer approach for the Sort Transformed Array problem, and why might some candidates incorrectly think it is higher?

medium

A. O(n) for processing plus O(n) auxiliary space for the output array.

B. O(n log n) because sorting is required after transformation.

C. O(n²) because each element is compared with every other element during merging.

D. O(n) because each element is processed exactly once using two pointers.

Solution

1. Step 1: Identify loop iterations

   The two-pointer approach processes each element once, moving pointers inward until they meet, resulting in O(n) iterations.

2. Step 2: Understand no sorting needed

   Because the input is sorted and the parabola shape is leveraged, no sorting step is required, avoiding O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear scan with two pointers, no nested loops [OK]

Hint: Two pointers scan array once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting after transformation is needed
• Confusing auxiliary space with time complexity

5. Consider the following buggy implementation of wiggle sort. Which line contains the subtle bug that causes the algorithm to fail on inputs with duplicates?

medium

A. Line 9: def virtual_index(i): return (1 + 2 * i) % (n | 1)

B. Line 3: nums.sort()

C. Line 4: median = nums[n // 2]

D. Line 15: elif nums[vi] < median:

Solution

1. Step 1: Identify median calculation

   The median is incorrectly chosen as nums[n // 2], which is the upper median for even-length arrays, but the algorithm requires the lower median nums[(n - 1) // 2].

2. Step 2: Understand impact on partitioning

   Incorrect median causes wrong partitioning of elements equal to median, leading to clustering and violation of wiggle property especially with duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct median index is (n - 1) // 2, not n // 2 [OK]

Hint: Median index off-by-one breaks partitioning with duplicates [OK]

Common Mistakes:

• Using n//2 instead of (n-1)//2 for median
• Ignoring duplicates in partitioning
• Misusing virtual indexing