LeetCode 1217 - Minimum Cost to Move Chips to The Same Position

LeetCode Problem 1217

Difficulty: 🟢 Easy
Topics: Array, Math, Greedy

Solution

Problem Understanding

The problem asks us to move n chips located at various positions along a one-dimensional line so that they all end up at the same position. Each chip can be moved either by 2 units at zero cost or by 1 unit at a cost of 1. The input is an array of integers, position, where position[i] denotes the position of the i-th chip. The output is a single integer representing the minimum cost required to move all chips to a common position.

The constraints tell us that the array length is modest (1 <= position.length <= 100), but the positions themselves can be very large (1 <= position[i] <= 10^9). This indicates that we cannot rely on algorithms that iterate over every possible position between the minimum and maximum chip positions, since the range can be extremely large. Instead, we need to exploit some property of the moves themselves.

Important edge cases include arrays where all chips are already at the same position (minimum cost = 0), arrays with only one chip, arrays with chips at extremely distant positions (e.g., [1, 1000000000]), and arrays where all chips are on either even or odd positions.

The critical observation is that moving a chip by 2 units costs 0, which means chips can freely move between positions of the same parity (even ↔ even or odd ↔ odd) without incurring any cost. Moving between even and odd positions costs 1. This parity insight is the key to solving the problem efficiently.

Approaches

A brute-force approach would consider every position between the minimum and maximum values of the array and compute the total cost to move all chips to that position. For each chip, the cost would be 0 if the difference is even and 1 if the difference is odd. While correct, this approach is inefficient because the position values can be up to 10^9, making iterating over every possible position infeasible.

The optimal approach leverages the parity property. We only need to count how many chips are at even positions and how many are at odd positions. Moving all chips to an even position incurs a cost equal to the number of chips at odd positions, and moving all chips to an odd position incurs a cost equal to the number of chips at even positions. Therefore, the minimum cost is simply the smaller of the two counts.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((max(position)-min(position)) * n)	O(1)	Iterates over every position and sums costs, infeasible for large positions
Optimal	O(n)	O(1)	Counts chips at even and odd positions, then takes the min count

Algorithm Walkthrough

1. Initialize two counters: even_count and odd_count to zero. These will track the number of chips at even and odd positions respectively.
2. Iterate through the position array.
3. For each pos, check if it is even or odd. If pos % 2 == 0, increment even_count. Otherwise, increment odd_count.
4. After iterating through all chips, compute the minimum cost as min(even_count, odd_count).
5. Return the minimum cost.

Why it works: Chips can move freely between positions of the same parity at zero cost. Therefore, the only cost comes from moving chips across parity boundaries. By counting the number of chips in each parity group, we know exactly how many must incur a cost to unify all chips at a single parity, guaranteeing the minimum cost solution.

Python Solution

from typing import List

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        even_count = 0
        odd_count = 0
        
        for pos in position:
            if pos % 2 == 0:
                even_count += 1
            else:
                odd_count += 1
        
        return min(even_count, odd_count)

The implementation follows the algorithm directly. We iterate over each chip, counting the number of chips in even and odd positions. The result is simply the smaller of the two counts, representing the minimum number of chips that must move across parity boundaries.

Go Solution

func minCostToMoveChips(position []int) int {
    evenCount := 0
    oddCount := 0
    
    for _, pos := range position {
        if pos%2 == 0 {
            evenCount++
        } else {
            oddCount++
        }
    }
    
    if evenCount < oddCount {
        return evenCount
    }
    return oddCount
}

In Go, we iterate through the slice and maintain two integer counters for even and odd positions. The min comparison is done using a simple if statement since Go lacks a built-in min function for integers. Edge cases like empty slices are not possible due to the constraints.

Worked Examples

Example 1: position = [1,2,3]

Chip	Position	Parity	Counts
1	1	Odd	even=0, odd=1
2	2	Even	even=1, odd=1
3	3	Odd	even=1, odd=2

Minimum cost = min(even_count, odd_count) = min(1, 2) = 1

Example 2: position = [2,2,2,3,3]

Chip	Position	Parity	Counts
1	2	Even	even=1, odd=0
2	2	Even	even=2, odd=0
3	2	Even	even=3, odd=0
4	3	Odd	even=3, odd=1
5	3	Odd	even=3, odd=2

Minimum cost = min(3, 2) = 2

Example 3: position = [1,1000000000]

Chip	Position	Parity	Counts
1	1	Odd	even=0, odd=1
2	1000000000	Even	even=1, odd=1

Minimum cost = min(1, 1) = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the position array, counting parity
Space	O(1)	Only two integer counters are used, regardless of input size

The complexity is optimal because we only need a single iteration and no additional data structures beyond counters.

Test Cases

# test cases
assert Solution().minCostToMoveChips([1,2,3]) == 1  # mix of even and odd
assert Solution().minCostToMoveChips([2,2,2,3,3]) == 2  # multiple chips at same positions
assert Solution().minCostToMoveChips([1,1000000000]) == 1  # large difference
assert Solution().minCostToMoveChips([2,4,6,8]) == 0  # all even, no cost
assert Solution().minCostToMoveChips([1,3,5,7]) == 0  # all odd, no cost
assert Solution().minCostToMoveChips([1]) == 0  # single chip
assert Solution().minCostToMoveChips([1,2]) == 1  # simplest cross parity

Test	Why
[1,2,3]	Mix of even and odd positions
[2,2,2,3,3]	Multiple chips at same positions with parity difference
[1,1000000000]	Large numerical gap, tests algorithm avoids brute force
[2,4,6,8]	All chips even, should incur zero cost
[1,3,5,7]	All chips odd, should incur zero cost
[1]	Single chip, minimum cost is zero
[1,2]	Smallest cross-parity case

Edge Cases

A key edge case is when all chips are already at the same position. In this scenario, either all chips are even or all are odd, and our counters reflect this, resulting in a minimum cost of zero.

Another edge case is when chips occupy extremely large positions but are still minimal in number, such as [1, 1000000000]. Our algorithm only cares about parity, so the size of the number does not affect correctness, avoiding performance issues.

A third edge case is when all chips are in one parity group and one chip is in the other parity group. For instance, [2,4,6,1]. The minimum cost should be 1, corresponding to moving the single odd chip to an even position. The algorithm handles this naturally because it simply takes the minimum of the counts.