Minimum Absolute Difference

▶

Steps

setup

Start with the unsorted array

We begin with the input array in its original unsorted state: [4, 2, 1, 3].

💡 Seeing the unsorted array helps understand why sorting is necessary to simplify difference calculations.

Line:

arr = [4, 2, 1, 3]

💡 The problem is harder to solve directly on an unsorted array.

expand

Sort the array in ascending order

The array is sorted to become [1, 2, 3, 4], enabling efficient adjacent comparisons.

💡 Sorting arranges elements so the minimum difference must be between neighbors.

Line:

arr.sort()

💡 Sorting reduces the problem to checking only adjacent pairs.

setup

Initialize min_diff to infinity

We set min_diff to a very large number to ensure any found difference will be smaller.

💡 Initializing min_diff this way allows us to update it with any smaller difference found.

Line:

min_diff = float('inf')

💡 min_diff will track the smallest difference found so far.

compare

Start comparing first adjacent pair (i=0)

Pointer i is at index 0 comparing elements 1 and 2.

💡 We compare adjacent elements to find their difference.

Line:

diff = arr[i + 1] - arr[i]

💡 The difference between 1 and 2 is 1.

compare

Check if difference equals 1 for early exit

Since the difference is 1, the smallest possible, we return 1 immediately.

💡 Finding difference 1 means no smaller difference can exist.

Line:

if diff == 1:
    return 1

💡 Early exit optimizes performance by stopping unnecessary checks.

reconstruct

Return the minimum absolute difference

The function returns 1 as the minimum absolute difference found.

💡 Returning early saves time and confirms the answer.

Line:

return 1

💡 The minimum difference is confirmed without scanning all pairs.

def minimum_abs_difference(arr):  # STEP 1-2
    arr.sort()  # STEP 2
    min_diff = float('inf')  # STEP 3
    for i in range(len(arr) - 1):  # STEP 4
        diff = arr[i + 1] - arr[i]  # STEP 4
        if diff == 1:  # STEP 5
            return 1  # STEP 5
        if diff < min_diff:  # (not reached in this input)
            min_diff = diff
    return min_diff  # (not reached in this input)

if __name__ == '__main__':  # Driver code
    arr = [4, 2, 1, 3]  # STEP 1
    print(minimum_abs_difference(arr))  # Output: 1

📊

Minimum Absolute Difference - Watch the Algorithm Execute, Step by Step

Watching each step shows how sorting simplifies the problem and how scanning adjacent pairs efficiently finds the minimum difference.

setup

4

0

2

1

1

2

3

3

Result: "undefined"

expand

1

0

2

1

3

2

4

3

Result: "undefined"

setup

1

0

2

1

3

2

4

3

Result: "min_diff = ∞"

compare

i

1

0

2

1

3

2

4

3

Result: "min_diff = ∞"

compare

i

1

0

2

1

3

2

4

3

Result: "answer = 1"

record

1

0

2

1

3

2

4

3

Result: "answer = 1"

Key Takeaways

✓ Sorting the array transforms the problem into checking only adjacent pairs.

Without sorting, you'd have to check all pairs, which is inefficient and harder to visualize.

✓ The pointer 'i' moves sequentially to compare each adjacent pair, showing a simple linear scan.

This linear scan is easy to follow visually and reveals how the minimum difference is found step-by-step.

✓ Early exit when difference equals 1 optimizes the algorithm by stopping unnecessary comparisons.

This decision is hard to spot in code alone but clear when watching the pointer stop immediately.

Practice

1. Consider the following Python function that finds the minimum time difference between time points. What is the returned value when the input is ["01:01", "02:01", "01:02"]?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        if seen[total]:
            return 0
        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

easy

A. 59

B. 0

C. 60

D. 1

Solution

1. Step 1: Convert times to minutes and mark seen

   "01:01" -> 61, "02:01" -> 121, "01:02" -> 62; all unique, so no early return 0.

2. Step 2: Iterate over seen array to find minimum adjacent difference

   Adjacent times are 61 and 62 (diff 1), 62 and 121 (diff 59). Minimum difference is 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Minimum adjacent difference found is 1 minute [OK]

Hint: Check adjacent differences after sorting times [OK]

Common Mistakes:

• Confusing difference between 61 and 121 as minimum
• Forgetting to check circular difference
• Returning 0 incorrectly when no duplicates

2. 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

3. You are given an array containing only three distinct values representing colors: red, white, and blue. The goal is to sort the array so that all reds come first, followed by whites, then blues, in a single pass with constant extra space. Which algorithmic approach guarantees this optimal solution?

easy

A. Use a standard comparison-based sort like quicksort or mergesort to sort the array.

B. Use a three-pointer partitioning approach that rearranges elements in one pass, known as the Dutch National Flag algorithm.

C. Count the occurrences of each color and then overwrite the array in multiple passes.

D. Use dynamic programming to decide the position of each color based on previous states.

Solution

1. Step 1: Understand the problem constraints

   The problem requires sorting three distinct values in a single pass with O(1) extra space.

2. Step 2: Identify the algorithm that meets these constraints

   The Dutch National Flag algorithm uses three pointers to partition the array in one pass without extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   One-pass, constant space sorting of three distinct values matches Dutch National Flag algorithm [OK]

Hint: One-pass, three-pointer partitioning solves this optimally [OK]

Common Mistakes:

• Thinking counting sort is optimal despite multiple passes
• Assuming comparison-based sorts are needed
• Confusing DP with sorting problems

4. What is the time complexity of the optimal wiggle sort algorithm that uses sorting, median finding, and in-place three-way partitioning with virtual indexing on an input array of length n?

medium

A. O(n log n) because median finding requires sorting and partitioning is linear

B. O(n) because partitioning and virtual indexing are linear time operations

C. O(n^2) because of repeated swaps during three-way partitioning

D. O(n log n) due to the initial sorting step dominating the runtime

Solution

1. Step 1: Identify the dominant operation

   The algorithm first sorts the array, which takes O(n log n) time.

2. Step 2: Analyze partitioning and median finding

   Median is found by indexing the sorted array (O(1)), and three-way partitioning with virtual indexing runs in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so overall complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity despite linear partitioning [OK]

Common Mistakes:

• Assuming median finding is O(n) without sorting
• Confusing partitioning swaps as quadratic
• Ignoring sorting step's cost

5. Suppose the problem changes: now you must sort each diagonal but allow elements to be reused multiple times (i.e., duplicates can be placed anywhere along the diagonal). Which modification to the algorithm correctly handles this variant efficiently?

hard

A. Sort each diagonal once and store sorted arrays; assign elements from these arrays repeatedly as needed.

B. Use counting sort per diagonal to handle duplicates efficiently and assign elements accordingly.

C. Use the same min-heap approach but skip popping elements to allow reuse.

D. Apply dynamic programming to track reuse counts and reconstruct diagonals with duplicates.

Solution

1. Step 1: Recognize reuse implies duplicates can appear multiple times

   Min-heaps popping elements once won't allow reuse; we need a method that counts frequencies.

2. Step 2: Use counting sort per diagonal

   Counting sort efficiently handles duplicates by frequency counts, allowing reuse without repeated heap operations.

3. Step 3: Assign elements back using frequency counts

   Reconstruct diagonals by placing elements according to counts, supporting reuse efficiently.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting sort suits duplicates and reuse better than heap popping [OK]

Hint: Counting sort handles duplicates and reuse efficiently [OK]

Common Mistakes:

• Trying to reuse popped heap elements
• Re-sorting entire matrix repeatedly
• Using DP unnecessarily complicates solution