Magnetic Force Between Two Balls

▶

Steps

setup

Initialize and Sort Positions

The input positions array is sorted to prepare for binary search on distances. The initial search range is set from 1 to the maximum possible distance between the first and last positions.

💡 Sorting ensures positions are in ascending order, which is essential for the greedy feasibility check to work correctly.

Line:

position.sort()
low, high = 1, position[-1] - position[0]

💡 Sorting and setting the initial search boundaries define the problem space for binary searching the answer.

compare

Calculate Midpoint Distance (mid = 3)

Calculate the midpoint of the current search range (1 to 6), which is 3. This distance is tested for feasibility to place 3 balls with at least 3 units apart.

💡 Midpoint represents the candidate minimum distance to check if it is possible to place all balls accordingly.

Line:

mid = (low + high) // 2  # mid = 3

💡 Choosing mid divides the search space and focuses the feasibility check on a specific candidate distance.

compare

Feasibility Check: Place First Ball at Position 1

Start placing balls greedily. The first ball is placed at position 1 by default.

💡 The first ball placement sets the baseline for checking subsequent placements at the candidate distance.

Line:

count = 1
last_pos = position[0]  # last_pos = 1

💡 Initial placement is always at the first position in the sorted array.

compare

Feasibility Check: Try Placing Second Ball at Position 4

Check position 2: distance 2-1=1 < 3, skip. Check position 3: distance 3-1=2 < 3, skip. Check position 4: distance 4-1=3 >= 3, place second ball here.

💡 Only positions at least mid distance apart from last placed ball are valid for placement.

Line:

for pos in position[1:]:
  if pos - last_pos >= mid:
    count += 1
    last_pos = pos

💡 Greedy placement ensures balls are as close as possible but at least mid apart.

compare

Feasibility Check: Place Third Ball at Position 7 and Early Stop

Check position 7: distance 7-4=3 >= 3, place third ball here. Since 3 balls placed, feasibility check returns True early.

💡 Early stopping avoids unnecessary checks once feasibility is confirmed.

Line:

if count == m:
  return True  # Early stop

💡 Early stopping optimizes the feasibility check by halting once the goal is met.

shrink

Update Result and Search Higher Distances

Since mid=3 is feasible, update result to 3 and move low to mid+1=4 to try larger distances.

💡 Updating result ensures the largest feasible distance found so far is saved.

Line:

if can_place(mid):
  result = mid
  low = mid + 1

💡 Binary search narrows the search space towards larger feasible distances.

compare

Calculate Midpoint Distance (mid = 5)

Calculate new mid = (4 + 6) // 2 = 5 to test feasibility of placing balls at least 5 units apart.

💡 Midpoint recalculates candidate distance in the updated search space.

Line:

mid = (low + high) // 2  # mid = 5

💡 Binary search continues to narrow down the answer space.

compare

Feasibility Check: Place Balls with Distance 5 - Fail

Place first ball at 1. Next positions 2,3,4 are too close. Position 7: 7-1=6 >=5, place second ball. Only 2 balls placed, less than 3 required, so fail.

💡 Failing feasibility means distance 5 is too large to place all balls.

Line:

for pos in position[1:]:
  if pos - last_pos >= mid:
    count += 1
    last_pos = pos
if count < m:
  return False

💡 This step shows how feasibility check prunes the search space by eliminating impossible distances.

shrink

Search Lower Distances After Failure

Since mid=5 is not feasible, update high to mid-1=4 to try smaller distances.

💡 Adjusting the search space to smaller distances after failure narrows down the answer.

Line:

else:
  high = mid - 1

💡 Binary search eliminates the right half of the search space after failure.

compare

Calculate Midpoint Distance (mid = 4)

Calculate mid = (4 + 4) // 2 = 4 to test feasibility of placing balls at least 4 units apart.

💡 Midpoint recalculates candidate distance in the narrowed search space.

Line:

mid = (low + high) // 2  # mid = 4

💡 Binary search continues to test candidate distances.

compare

Feasibility Check: Place Balls with Distance 4 - Fail

Place first ball at 1. Positions 2,3,4 too close. Position 7: 7-1=6 >=4, place second ball. Only 2 balls placed, less than 3 required, so fail.

💡 Distance 4 is still too large to place all balls.

Line:

for pos in position[1:]:
  if pos - last_pos >= mid:
    count += 1
    last_pos = pos
if count < m:
  return False

💡 This confirms the maximum minimum distance is less than 4.

shrink

Search Lower Distances After Failure

Since mid=4 is not feasible, update high to mid-1=3 to try smaller distances.

💡 Adjusting the search space to smaller distances after failure narrows down the answer.

Line:

else:
  high = mid - 1

💡 Binary search terminates when low exceeds high, finalizing the answer.

reconstruct

Return Final Result

Binary search loop ends as low (4) > high (3). The last recorded feasible distance is 3, which is returned as the maximum minimum distance.

💡 The result variable holds the largest minimum distance found feasible during the search.

Line:

return result  # result = 3

💡 The algorithm successfully finds the maximum minimum distance by searching the answer space.

def maxDistanceOptimized(position, m):
    position.sort()  # STEP 1
    def can_place(distance):
        count = 1  # STEP 3
        last_pos = position[0]  # STEP 3
        for pos in position[1:]:  # STEP 4-5
            if pos - last_pos >= distance:
                count += 1
                last_pos = pos
                if count == m:  # Early stop
                    return True  # STEP 5
        return False  # STEP 8,11
    low, high = 1, position[-1] - position[0]  # STEP 1
    result = 0
    while low <= high:  # STEP 2,6,9,12
        mid = (low + high) // 2  # STEP 2,6,9,12
        if can_place(mid):  # STEP 5,6,10
            result = mid  # STEP 6
            low = mid + 1  # STEP 6
        else:
            high = mid - 1  # STEP 9,12
    return result  # STEP 13

if __name__ == '__main__':
    pos = [1,2,3,4,7]
    m = 3
    print(maxDistanceOptimized(pos, m))  # Output: 3

📊

Magnetic Force Between Two Balls - Watch the Algorithm Execute, Step by Step

Watching each binary search iteration and feasibility check reveals how the algorithm efficiently finds the largest minimum distance without brute forcing all possibilities.

1

0

lo

2

1

3

2

4

3

7

4

Next: lo=1 hi=6

Target: 3

1

0

lo

2

1

3

2

mid

4

3

7

4

mid[3]=3 - candidate distance to test

Next: lo=1 hi=6

Target: 3

1

0

lo

2

1

3

2

mid

4

3

7

4

mid[3]=3 - starting feasibility check

Next: lo=1 hi=6

Target: 3

1

0

lo

2

1

3

2

mid

4

3

7

4

mid[3]=3 - second ball placed at position 4

Next: lo=1 hi=6

Target: 3

1

0

lo

2

1

3

2

mid

4

3

7

4

mid[3]=3 - feasible to place all balls at distance 3

Next: lo=1 hi=6

Target: 3

1

0

2

1

3

2

mid

4

3

lo

7

4

mid[3]=3 - feasible, search higher

Next: lo=4 hi=6

Target: 5

1

0

2

1

3

2

4

3

lo

7

4

Next: lo=4 hi=6

Target: 5

1

0

2

1

3

2

4

3

lo

7

4

Next: lo=4 hi=6

Target: 5

1

0

2

1

3

2

4

3

lo

7

4

Next: lo=4 hi=4

Target: 4

1

0

2

1

3

2

4

3

lo/mid/hi

7

4

mid[4]=4 - candidate distance to test

Next: lo=4 hi=4

Target: 4

1

0

2

1

3

2

4

3

lo/mid/hi

7

4

mid[4]=4 - not feasible to place all balls at distance 4

Next: lo=4 hi=4

Target: 4

1

0

2

1

3

2

4

3

lo/mid/hi

7

4

mid[4]=4 - not feasible, search lower

Next: lo=4 hi=3

1

0

2

1

3

2

hi

4

3

lo

7

4

Next: lo=4 hi=3

Key Takeaways

✓ Binary search on the answer space efficiently finds the maximum minimum distance without checking every possibility.

Reading code alone can obscure how the search space shrinks and how feasibility checks guide the search.

✓ Greedy feasibility checks with early stopping quickly confirm if a candidate distance can place all balls.

Visualizing ball placements clarifies why early stopping saves time and how greedy placement works.

✓ Adjusting low and high based on feasibility results narrows the search space until the optimal distance is found.

Seeing the search space boundaries move step-by-step reveals the binary search logic more clearly than code.

Practice

1. Consider the following Python function that finds the kth positive missing number from a sorted array arr. What is the returned value when calling findKthPositive([2, 4, 7], 3)?

def findKthPositive(arr, k):
    n = len(arr)
    total_missing = arr[-1] - n
    if k > total_missing:
        return arr[-1] + (k - total_missing)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            left = mid + 1
        else:
            right = mid - 1
    return arr[right] + (k - (arr[right] - (right + 1)))

easy

A. 5

B. 8

C. 9

D. 7

Solution

1. Step 1: Calculate total missing numbers

   Array length n=3, arr[-1]=7, total_missing = 7 - 3 = 4. Since k=3 ≤ 4, proceed with binary search.

2. Step 2: Perform binary search iterations

   Initial left=0, right=2. - mid=1, missing=arr[1] - (1+1) = 4 - 2 = 2 < 3 -> left=2 - mid=2, missing=arr[2] - (2+1) = 7 - 3 = 4 ≥ 3 -> right=1 Loop ends as left=2 > right=1. Return arr[right] + (k - (arr[right] - (right + 1))) = arr[1] + (3 - (4 - 2)) = 4 + (3 - 2) = 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search narrows to index 1, final missing number is 5 [OK]

Hint: Trace missing count at mid carefully [OK]

Common Mistakes:

• Off-by-one in missing calculation
• Returning arr[left] instead of arr[right]
• Miscomputing missing count as arr[mid] - mid

2. Consider the following buggy code snippet intended to find the first and last positions of a target in a sorted array. What is the bug?

medium

A. The binary search stops immediately after finding any occurrence, not the first or last

B. The initial values of start and end are incorrectly set

C. The mid calculation can cause overflow for large indices

D. The while loops expanding boundaries do not check array bounds before accessing indices

Solution

1. Step 1: Examine boundary expansion loops

   Loops check nums[start - 1] and nums[end + 1] without verifying indices are within array bounds.

2. Step 2: Identify potential index out of range error

   If start=0 or end=len(nums)-1, accessing start-1 or end+1 causes IndexError.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary checks missing before array access [OK]

Hint: Always check array bounds before accessing neighbors [OK]

Common Mistakes:

• Stopping binary search early
• Ignoring boundary checks
• Incorrect mid calculation

3. What is the time complexity of the optimal binary search algorithm that treats an m x n 2D matrix as a 1D sorted array to search for a target?

medium

A. O(log(m * n))

B. O(m * n)

C. O(m * log n)

D. O(log m + log n)

Solution

1. Step 1: Understand the search space size

   The matrix has m*n elements, treated as a sorted 1D array.

2. Step 2: Apply binary search complexity

   Binary search on an array of size m*n takes O(log(m*n)) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step, log scale [OK]

Hint: Binary search complexity depends on total elements, not rows or columns separately [OK]

Common Mistakes:

• Confusing with O(m*n) brute force
• Thinking binary search per row is O(m log n)
• Adding logs incorrectly as O(log m + log n)

4. Consider the following buggy code snippet for searching a target in a rotated sorted array with duplicates. Which line contains the subtle bug that can cause infinite loops or incorrect results?

medium

A. Line 9: if nums[mid] == target: return True

B. Line 7: mid = (left + right) // 2

C. Line 13: if nums[left] <= target < nums[mid]: right = mid - 1

D. Line 4: while left < right and nums[left] == nums[left + 1]: left += 1

Solution

1. Step 1: Identify duplicate skipping logic

   The code only skips duplicates from the left side, ignoring duplicates on the right side.

2. Step 2: Understand impact of skipping duplicates only on one side

   If duplicates exist on the right side, pointers may not move correctly, causing infinite loops or incorrect search decisions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Skipping duplicates only on one side breaks correctness [OK]

Hint: Must skip duplicates from both ends to avoid infinite loops [OK]

Common Mistakes:

• Skipping duplicates only from left or right
• Not checking target at mid first
• Incorrect pointer updates

5. Suppose the problem is modified so that packages can be shipped in any order (not necessarily the given order) within the given days. Which of the following approaches correctly finds the minimal ship capacity under this new constraint?

hard

A. Use dynamic programming to assign packages to days minimizing maximum load per day, combined with binary search on capacity

B. Sort packages in descending order and use a greedy bin-packing heuristic combined with binary search on capacity

C. Use a simple greedy approach assigning packages to days in any order without binary search

D. Use the same binary search on capacity with the original feasibility check since order doesn't matter

Solution

1. Step 1: Understand the relaxed constraint

   Packages can be shipped in any order, so the problem becomes a variant of multi-way partition or bin packing minimizing max load.

2. Step 2: Identify correct approach

   Binary search on capacity still applies, but feasibility check requires DP or backtracking to assign packages optimally to days, as greedy heuristics may fail.

3. Step 3: Why other options fail

   Original feasibility check assumes fixed order; greedy heuristics are approximate and may not find minimal capacity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP feasibility check with binary search needed for unordered assignment [OK]

Hint: Order relaxation requires DP feasibility check, not simple greedy [OK]

Common Mistakes:

• Using original feasibility check ignoring order change
• Assuming greedy suffices
• Ignoring complexity increase