Make the Array Beautiful (Sort + Greedy)

🎯

Make the Array Beautiful (Sort + Greedy)

mediumSORT_SEARCHAmazonGoogle

Imagine you have a messy collection of colored beads on a string, and you want to rearrange them so that no two adjacent beads share the same color, making the string 'beautiful'.

💡 This problem requires combining sorting with a greedy approach to rearrange elements. Beginners often struggle because they try to solve it without sorting or fail to realize how sorting enables a simple greedy scan. Think of sorting as organizing beads by color frequency, then greedily placing the most frequent colors spaced apart to avoid adjacency.

📋

Problem Statement

Given an array of integers, rearrange the elements so that no two adjacent elements are equal. Return any such rearrangement if possible; otherwise, return an empty array.

1 ≤ n ≤ 10^50 ≤ array elements ≤ 10^9

💡

Example

Input"[1,1,2,2,3,3]"

Output[1,2,1,3,2,3]

One possible rearrangement where no two adjacent elements are equal.

• All elements are the same → return []
• Array of length 1 → return the array itself
• Array with two elements both equal → return []
• Array with multiple duplicates but rearrangement possible → return valid rearrangement

⚠️

Common Mistakes

Not checking if max frequency exceeds half the array length

Returns invalid rearrangement or crashes

✅ Add a frequency check before attempting rearrangement

Placing elements without spacing the most frequent ones first

Adjacent duplicates appear in output

✅ Place the most frequent elements at even indices first

Using brute force for large inputs

Time limit exceeded or program hangs

✅ Use sorting + greedy or heap approach for efficiency

Not handling edge cases like single element or all identical elements

Incorrect output or runtime errors

✅ Explicitly handle small arrays and check feasibility

🧠

Brute Force (Backtracking / Permutation Generation)

💡 This approach tries all permutations to find a valid rearrangement. It is impractical for large inputs but helps understand the problem constraints and correctness. Imagine trying every possible way to arrange beads on a string to see if any arrangement is beautiful.

Intuition

Try every possible ordering of the array and check if any ordering has no two adjacent equal elements.

Algorithm

1. Generate all permutations of the array.
2. For each permutation, check if any two adjacent elements are equal.
3. If a valid permutation is found, return it.
4. If none found, return an empty array.

💡 This approach is straightforward but inefficient because it blindly tries all possibilities without pruning.

</>

Code

from itertools import permutations

def make_array_beautiful_brute(arr):
    for perm in permutations(arr):
        if all(perm[i] != perm[i+1] for i in range(len(perm)-1)):
            return list(perm)
    return []

# Driver code
if __name__ == '__main__':
    arr = [1,1,2,2,3,3]
    print(make_array_beautiful_brute(arr))

Line Notes

from itertools import permutationsImport permutations to generate all possible orderings

for perm in permutations(arr)Try every possible arrangement of the array

if all(perm[i] != perm[i+1] for i in range(len(perm)-1))Check if no two adjacent elements are equal

return list(perm)Return the first valid permutation found

import java.util.*;

public class MakeArrayBeautifulBrute {
    public static List<Integer> makeBeautiful(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) list.add(num);
        List<List<Integer>> perms = new ArrayList<>();
        permute(list, 0, perms);
        for (List<Integer> perm : perms) {
            if (isBeautiful(perm)) return perm;
        }
        return new ArrayList<>();
    }

    private static void permute(List<Integer> arr, int start, List<List<Integer>> res) {
        if (start == arr.size()) {
            res.add(new ArrayList<>(arr));
            return;
        }
        for (int i = start; i < arr.size(); i++) {
            Collections.swap(arr, start, i);
            permute(arr, start + 1, res);
            Collections.swap(arr, start, i);
        }
    }

    private static boolean isBeautiful(List<Integer> arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr.get(i).equals(arr.get(i + 1))) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,3};
        System.out.println(makeBeautiful(arr));
    }
}

Line Notes

permute(List<Integer> arr, int start, List<List<Integer>> res)Generate all permutations recursively

Collections.swap(arr, start, i)Swap elements to create new permutations

if (isBeautiful(perm)) return perm;Return the first valid permutation found

for (int i = 0; i < arr.size() - 1; i++)Check adjacent elements for equality

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

using namespace std;

bool isBeautiful(const vector<int>& arr) {
    for (int i = 0; i < (int)arr.size() - 1; i++) {
        if (arr[i] == arr[i + 1]) return false;
    }
    return true;
}

bool nextPermutation(vector<int>& arr) {
    return std::next_permutation(arr.begin(), arr.end());
}

vector<int> makeBeautifulBrute(vector<int> arr) {
    sort(arr.begin(), arr.end());
    do {
        if (isBeautiful(arr)) return arr;
    } while (nextPermutation(arr));
    return {};
}

int main() {
    vector<int> arr = {1,1,2,2,3,3};
    vector<int> res = makeBeautifulBrute(arr);
    if (res.empty()) cout << "[]" << endl;
    else {
        for (int x : res) cout << x << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

sort(arr.begin(), arr.end())Sort to generate permutations in lex order

do { ... } while (nextPermutation(arr))Try all permutations using STL next_permutation

if (isBeautiful(arr)) return arr;Return first valid permutation found

for (int i = 0; i < (int)arr.size() - 1; i++)Check adjacent elements for equality

function makeBeautifulBrute(arr) {
    function isBeautiful(a) {
        for (let i = 0; i < a.length - 1; i++) {
            if (a[i] === a[i + 1]) return false;
        }
        return true;
    }

    function permute(a, l, r) {
        if (l === r) {
            if (isBeautiful(a)) return a.slice();
            return null;
        }
        for (let i = l; i <= r; i++) {
            [a[l], a[i]] = [a[i], a[l]];
            let res = permute(a, l + 1, r);
            if (res) return res;
            [a[l], a[i]] = [a[i], a[l]];
        }
        return null;
    }

    return permute(arr, 0, arr.length - 1) || [];
}

// Test
console.log(makeBeautifulBrute([1,1,2,2,3,3]));

Line Notes

function isBeautiful(a)Helper to check no two adjacent equal elements

function permute(a, l, r)Recursive function to generate permutations

if (l === r)Base case: one permutation generated

if (res) return res;Return first valid permutation found immediately

⏱

Complexity

TimeO(n! * n)

SpaceO(n)

Generating all permutations is factorial time, and checking adjacency is linear per permutation.

💡 For n=10, this means over 3 million permutations, which is infeasible.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem constraints.

🧠

Sorting + Greedy Rearrangement Using Frequency Count

💡 Sorting the array and counting frequencies helps us understand if a valid rearrangement is possible and guides a greedy approach to build the answer. Think of it as first organizing beads by color frequency, then placing the most frequent colors spaced apart to avoid adjacency.

Intuition

If the most frequent element appears more than half the array length, no valid rearrangement exists. Otherwise, place the most frequent elements first at even indices, then fill remaining positions.

Algorithm

1. Count frequency of each element.
2. Check if any element frequency > (n+1)//2; if yes, return empty array.
3. Sort elements by frequency descending.
4. Place the most frequent elements at even indices (0,2,4...) in the result array.
5. Place remaining elements in the leftover positions.

💡 This approach uses sorting and a greedy placement strategy to ensure no two adjacent elements are equal.

</>

Code

from collections import Counter

def make_array_beautiful(arr):
    n = len(arr)
    freq = Counter(arr)
    max_freq = max(freq.values())
    if max_freq > (n + 1) // 2:
        return []
    sorted_items = sorted(freq.items(), key=lambda x: -x[1])
    res = [0] * n
    idx = 0
    for num, count in sorted_items:
        for _ in range(count):
            res[idx] = num
            idx += 2
            if idx >= n:
                idx = 1
    return res

# Driver code
if __name__ == '__main__':
    arr = [1,1,2,2,3,3]
    print(make_array_beautiful(arr))

Line Notes

freq = Counter(arr)Count frequency of each element to identify constraints

max_freq = max(freq.values())Find the highest frequency to check feasibility

if max_freq > (n + 1) // 2If any element appears too often, no valid arrangement exists

for num, count in sorted_itemsPlace elements starting from the most frequent

import java.util.*;

public class MakeArrayBeautiful {
    public static int[] makeBeautiful(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) freq.put(num, freq.getOrDefault(num, 0) + 1);
        int maxFreq = Collections.max(freq.values());
        if (maxFreq > (n + 1) / 2) return new int[0];

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(freq.entrySet());
        list.sort((a, b) -> b.getValue() - a.getValue());

        int[] res = new int[n];
        int idx = 0;
        for (Map.Entry<Integer, Integer> entry : list) {
            int num = entry.getKey();
            int count = entry.getValue();
            for (int i = 0; i < count; i++) {
                res[idx] = num;
                idx += 2;
                if (idx >= n) idx = 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,3};
        System.out.println(Arrays.toString(makeBeautiful(arr)));
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>()Count frequencies of elements

if (maxFreq > (n + 1) / 2) return new int[0]Check if rearrangement is impossible

list.sort((a, b) -> b.getValue() - a.getValue())Sort elements by descending frequency

idx += 2; if (idx >= n) idx = 1;Place elements at even indices first, then odd

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

using namespace std;

vector<int> makeBeautiful(vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> freq;
    for (int x : arr) freq[x]++;
    int maxFreq = 0;
    for (auto& p : freq) maxFreq = max(maxFreq, p.second);
    if (maxFreq > (n + 1) / 2) return {};

    vector<pair<int,int>> freqVec(freq.begin(), freq.end());
    sort(freqVec.begin(), freqVec.end(), [](auto& a, auto& b) { return a.second > b.second; });

    vector<int> res(n);
    int idx = 0;
    for (auto& p : freqVec) {
        int num = p.first, count = p.second;
        for (int i = 0; i < count; i++) {
            res[idx] = num;
            idx += 2;
            if (idx >= n) idx = 1;
        }
    }
    return res;
}

int main() {
    vector<int> arr = {1,1,2,2,3,3};
    vector<int> res = makeBeautiful(arr);
    if (res.empty()) cout << "[]" << endl;
    else {
        for (int x : res) cout << x << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

unordered_map<int, int> freq;Count frequencies efficiently

if (maxFreq > (n + 1) / 2) return {};Return empty if rearrangement impossible

sort(freqVec.begin(), freqVec.end(), ...Sort elements by frequency descending

idx += 2; if (idx >= n) idx = 1;Place elements at even indices first, then odd

function makeArrayBeautiful(arr) {
    const freq = new Map();
    for (const num of arr) freq.set(num, (freq.get(num) || 0) + 1);
    const n = arr.length;
    let maxFreq = 0;
    for (const count of freq.values()) maxFreq = Math.max(maxFreq, count);
    if (maxFreq > Math.floor((n + 1) / 2)) return [];

    const sorted = [...freq.entries()].sort((a, b) => b[1] - a[1]);
    const res = new Array(n);
    let idx = 0;
    for (const [num, count] of sorted) {
        for (let i = 0; i < count; i++) {
            res[idx] = num;
            idx += 2;
            if (idx >= n) idx = 1;
        }
    }
    return res;
}

// Test
console.log(makeArrayBeautiful([1,1,2,2,3,3]));

Line Notes

const freq = new Map();Count frequencies of each element

if (maxFreq > Math.floor((n + 1) / 2)) return [];Check if rearrangement is impossible

const sorted = [...freq.entries()].sort(...)Sort elements by descending frequency

idx += 2; if (idx >= n) idx = 1;Place elements at even indices first, then odd

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Counting frequencies is O(n), sorting frequencies O(k log k) where k ≤ n, and placing elements O(n).

💡 For n=100000, this approach is efficient and practical.

Interview Verdict: Accepted

This approach is efficient and works well for large inputs, making it suitable for interviews.

🧠

Optimized Greedy Using Max Heap (Priority Queue)

💡 Using a max heap to always pick the most frequent element available ensures no two adjacent elements are equal by alternating picks. This is like always choosing the two most common beads left to place next, ensuring spacing between identical beads.

Intuition

Always pick the two most frequent remaining elements and place them alternately to avoid adjacency of duplicates.

Algorithm

1. Count frequency of each element.
2. Push all elements with their frequencies into a max heap.
3. Pop two most frequent elements and append them to the result.
4. Decrease their counts and push back if still positive.
5. Repeat until heap is empty or one element remains.
6. If one element remains, check if its count is 1 and append it; else return empty.

💡 This approach ensures no two adjacent elements are equal by always alternating the most frequent elements.

</>

Code

from collections import Counter
import heapq

def make_array_beautiful_heap(arr):
    freq = Counter(arr)
    max_freq = max(freq.values())
    n = len(arr)
    if max_freq > (n + 1) // 2:
        return []
    heap = [(-count, num) for num, count in freq.items()]
    heapq.heapify(heap)
    res = []
    prev_count, prev_num = 0, None
    while heap:
        count, num = heapq.heappop(heap)
        res.append(num)
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_num))
        prev_count, prev_num = count + 1, num
    return res

# Driver code
if __name__ == '__main__':
    arr = [1,1,2,2,3,3]
    print(make_array_beautiful_heap(arr))

Line Notes

freq = Counter(arr)Count frequencies of elements

heap = [(-count, num) for num, count in freq.items()]Create max heap by negating counts

prev_count, prev_num = 0, NoneTrack previously used element to avoid adjacency

if prev_count < 0: heapq.heappush(heap, (prev_count, prev_num))Push back previous element if still available

import java.util.*;

public class MakeArrayBeautifulHeap {
    public static int[] makeBeautiful(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) freq.put(num, freq.getOrDefault(num, 0) + 1);
        int maxFreq = Collections.max(freq.values());
        if (maxFreq > (n + 1) / 2) return new int[0];

        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            maxHeap.offer(new int[]{entry.getValue(), entry.getKey()});
        }

        int[] res = new int[n];
        int idx = 0;
        int[] prev = {0, 0};

        while (!maxHeap.isEmpty()) {
            int[] curr = maxHeap.poll();
            res[idx++] = curr[1];
            curr[0]--;
            if (prev[0] > 0) maxHeap.offer(prev);
            prev = curr;
        }

        if (idx != n) return new int[0];
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,3};
        System.out.println(Arrays.toString(makeBeautiful(arr)));
    }
}

Line Notes

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0])Max heap based on frequency

int[] prev = {0, 0};Track previously used element and its count

if (prev[0] > 0) maxHeap.offer(prev);Push back previous element if still available

if (idx != n) return new int[0];Check if all elements placed successfully

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<int> makeBeautifulHeap(vector<int>& arr) {
    int n = arr.size();
    unordered_map<int, int> freq;
    for (int x : arr) freq[x]++;
    int maxFreq = 0;
    for (auto& p : freq) maxFreq = max(maxFreq, p.second);
    if (maxFreq > (n + 1) / 2) return {};

    priority_queue<pair<int,int>> maxHeap;
    for (auto& p : freq) maxHeap.push({p.second, p.first});

    vector<int> res;
    pair<int,int> prev = {0, 0};

    while (!maxHeap.empty()) {
        auto curr = maxHeap.top(); maxHeap.pop();
        res.push_back(curr.second);
        if (prev.first > 0) maxHeap.push(prev);
        curr.first--;
        prev = curr;
    }

    if ((int)res.size() != n) return {};
    return res;
}

int main() {
    vector<int> arr = {1,1,2,2,3,3};
    vector<int> res = makeBeautifulHeap(arr);
    if (res.empty()) cout << "[]" << endl;
    else {
        for (int x : res) cout << x << " ";
        cout << endl;
    }
    return 0;
}

Line Notes

priority_queue<pair<int,int>> maxHeap;Max heap stores frequency and element

pair<int,int> prev = {0, 0};Track previously used element to avoid adjacency

if (prev.first > 0) maxHeap.push(prev);Push back previous element if still available

if ((int)res.size() != n) return {};Verify all elements placed successfully

function makeArrayBeautifulHeap(arr) {
    const freq = new Map();
    for (const num of arr) freq.set(num, (freq.get(num) || 0) + 1);
    const n = arr.length;
    let maxFreq = 0;
    for (const count of freq.values()) maxFreq = Math.max(maxFreq, count);
    if (maxFreq > Math.floor((n + 1) / 2)) return [];

    const maxHeap = [];
    for (const [num, count] of freq.entries()) {
        maxHeap.push({num, count});
    }
    maxHeap.sort((a, b) => b.count - a.count);

    const res = [];
    let prev = null;

    while (maxHeap.length > 0) {
        let curr = maxHeap.shift();
        res.push(curr.num);
        if (prev !== null) {
            maxHeap.push(prev);
            maxHeap.sort((a, b) => b.count - a.count);
        }
        curr.count--;
        prev = curr.count > 0 ? curr : null;
    }

    if (res.length !== n) return [];
    return res;
}

// Test
console.log(makeArrayBeautifulHeap([1,1,2,2,3,3]));

Line Notes

const freq = new Map();Count frequencies of elements

if (maxFreq > Math.floor((n + 1) / 2)) return [];Check feasibility

maxHeap.sort((a, b) => b.count - a.count);Sort max heap by frequency descending

if (prev !== null) { maxHeap.push(prev); ... }Push back previously used element if still available

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Counting frequencies is O(n), heap operations O(log k) per element, where k is distinct elements.

💡 For large n but small k, this approach is very efficient.

Interview Verdict: Accepted

This approach is optimal for large inputs and dynamic scenarios, demonstrating mastery of greedy and heap data structures.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 (sorting + greedy) is usually best to code; approach 3 (heap) is good to discuss for optimization.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Sorting + Greedy	O(n log n)	O(n)	No	Yes	Code this approach in 95% of interviews
3. Max Heap Greedy	O(n log k)	O(k)	No	Yes	Discuss or code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews. Think of the problem as arranging beads so no two adjacent beads share the same color, and use sorting and greedy strategies to achieve this.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Present the sorting + greedy frequency approach as an efficient solution.Optionally discuss the heap-based approach for further optimization.Write clean, tested code and analyze complexity.

Time Allocation

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

What the Interviewer Tests

Ability to identify problem constraints, use sorting and greedy strategies, optimize with data structures, and write clean code.

Common Follow-ups

• What if the array is very large and streaming? → Use heap approach for dynamic updates.
• Can you return all valid rearrangements? → This is complex; usually only one valid rearrangement is required.

💡 These follow-ups test your ability to adapt solutions to constraints and think beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Need to rearrange array elements; 2) Avoid adjacent duplicates; 3) Frequency constraints matter; 4) Sorting or priority queue helps.

Signature Phrases

no two adjacent elements are equalrearrange the array

NOT This Pattern When

Problems that only require sorting or searching without adjacency constraints

Similar Problems

Rearrange String k Distance Apart - similar frequency and spacing constraintsTask Scheduler - scheduling tasks with cooldowns uses similar greedy + heap3Sum - uses sorting + two pointers but for sum problems

Practice

1. Consider the following Python code for generating the largest number from a list of integers. What is the output when the input is [3, 30, 34]?

from functools import cmp_to_key

def largestNumber(nums):
    nums_str = list(map(str, nums))

    def compare(a, b):
        return -1 if a + b > b + a else 1 if a + b < b + a else 0

    nums_str.sort(key=cmp_to_key(compare))
    if nums_str[0] == '0':
        return '0'
    return ''.join(nums_str)

print(largestNumber([3, 30, 34]))

easy

A. '34330'

B. '33034'

C. '33430'

D. '34303'

Solution

1. Step 1: Convert numbers to strings

   nums_str = ['3', '30', '34']

2. Step 2: Sort with custom comparator

   Compare pairs: - '3' + '30' = '330' vs '30' + '3' = '303' -> '330' > '303', so '3' before '30' - '34' + '3' = '343' vs '3' + '34' = '334' -> '343' > '334', so '34' before '3' - '34' + '30' = '3430' vs '30' + '34' = '3034' -> '3430' > '3034', so '34' before '30' Sorted order: ['34', '3', '30']

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation '34330' is largest [OK]

Hint: Compare concatenations a+b and b+a to order strings [OK]

Common Mistakes:

• Sorting lexicographically or numerically without custom comparator

2. Consider the following Python function to find the minimum absolute difference in an array. What is the returned value when the input is [4, 2, 1, 3]?

def minimum_abs_difference(arr):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff == 1:
            return 1
        if diff < min_diff:
            min_diff = diff
    return min_diff

print(minimum_abs_difference([4, 2, 1, 3]))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 2, 3, 4].

2. Step 2: Iterate and check adjacent differences

   Differences: 2-1=1 -> triggers early return 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Early exit on diff==1 returns 1 [OK]

Hint: Early exit returns 1 on first adjacent difference of 1 [OK]

Common Mistakes:

• Forgetting early exit
• Returning difference between non-adjacent pairs

3. Consider the following Python code implementing the optimal approach for relative sorting. Given arr1 = [3,1,2,2] and arr2 = [2,3], what is the final returned list?

easy

A. [2, 3, 1, 2]

B. [3, 2, 2, 1]

C. [2, 2, 3, 1]

D. [1, 2, 2, 3]

Solution

1. Step 1: Build frequency array for arr1

   arr1 = [3,1,2,2], max_val=3, freq = [0,1,2,1] (indices 0 to 3)

2. Step 2: Construct result using arr2 order then leftovers

   Output elements for arr2: 2 appears twice -> [2,2], 3 appears once -> [2,2,3]. Leftover is 1 once -> [2,2,3,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency counts and order match output [OK]

Hint: Trace frequency array and output order carefully [OK]

Common Mistakes:

• Appending leftover elements before arr2 order
• Miscounting frequencies or off-by-one in freq array
• Mixing order of arr2 elements in output

4. The following code attempts to find the minimum time difference between time points. Which line contains a subtle bug that causes incorrect results on inputs with duplicate times?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        seen[total] = True
    prev = -1
    first = -1
    min_diff = 1440
    for i in range(1440):
        if seen[i]:
            if prev != -1:
                min_diff = min(min_diff, i - prev)
            else:
                first = i
            prev = i
    min_diff = min(min_diff, 1440 - prev + first)
    return min_diff

medium

A. Line updating min_diff inside the loop

B. Line initializing prev = -1

C. Line that sets seen[total] = True without checking duplicates

D. Line computing min_diff with circular difference after the loop

Solution

1. Step 1: Check duplicate detection logic

   The code sets seen[total] = True but does not check if seen[total] was already True, missing duplicates.

2. Step 2: Consequence of missing duplicate check

   Without detecting duplicates, the function cannot return 0 early, causing wrong minimum difference on duplicate inputs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding a duplicate check before setting seen fixes the bug [OK]

Hint: Check for duplicate times before marking seen [OK]

Common Mistakes:

• Ignoring duplicates leads to wrong min difference
• Misplaced min_diff update
• Forgetting circular difference check

5. What is the worst-case time complexity of the optimal approach using binary search to find missing ranges in a sorted list of size n within the range [lower, upper]?

medium

A. O(n log n)

B. O((upper - lower) * log n)

C. O(n + log(upper - lower))

D. O(n log(upper - lower))

Solution

1. Step 1: Analyze binary search calls per iteration

   Each iteration advances pointer to next missing range start or after current number. Each bisect call is O(log n). Since pointer can advance by 1 in worst case, total iterations can be up to (upper - lower + 1).

2. Step 2: Combine iteration count and bisect cost

   In worst case, pointer advances one by one through the entire range, each bisect O(log n), total O((upper - lower) * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per number in range leads to O((upper - lower) log n) [OK]

Hint: Pointer can advance one by one, so multiply range size by log n [OK]

Common Mistakes:

• Assuming pointer always skips ahead by elements
• Confusing n and range size
• Ignoring worst-case pointer increments