Jobs

Interviews

Discussions

Super Washing Machines

Hard

Google

3 views

Topics:

ArraysGreedy Algorithms

You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any m (1 <= m <= n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.

Given an integer array machines representing the number of dresses in each washing machine from left to right on the line, return the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

Example 1:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

Example 2:

Input: machines = [0,3,0]
Output: 2
Explanation:
1st move:    0 <-- 3     0    =>    1     2     0
2nd move:    1     2 --> 0    =>    1     1     1

Example 3:

Input: machines = [0,2,0]
Output: -1
Explanation:
It's impossible to make all three washing machines have the same number of dresses.

Constraints:

n == machines.length
1 <= n <= 10⁴
0 <= machines[i] <= 10⁵

Super Washing Machines

Hard

Google

3 views

Topics:

ArraysGreedy Algorithms

You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any m (1 <= m <= n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.

Example 1:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

Example 2:

Input: machines = [0,3,0]
Output: 2
Explanation:
1st move:    0 <-- 3     0    =>    1     2     0
2nd move:    1     2 --> 0    =>    1     1     1

Example 3:

Input: machines = [0,2,0]
Output: -1
Explanation:
It's impossible to make all three washing machines have the same number of dresses.

Constraints:

n == machines.length
1 <= n <= 10⁴
0 <= machines[i] <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the number of dresses in each washing machine? Can a washing machine have a negative number of dresses?
Can the input array `machines` be empty or null? What should the output be in such cases?
If it's impossible to equalize the dresses in all machines, what value should I return? (e.g., -1, null, throw an exception)?
Is the number of washing machines guaranteed to be within a reasonable range (e.g., less than 10,000)? This might affect memory usage and algorithm choice.
Does the array `machines` only contain integers, or could there be floating-point values?

Brute Force Solution

Approach

The brute force method for this washing machine problem involves exploring all possible ways to redistribute dresses between the machines. We simulate moving dresses in different amounts between machines until all machines have the same number of dresses. We then find the minimum number of moves needed across all the possibilities that achieve balance.

Here's how the algorithm would work step-by-step:

First, figure out the average number of dresses each machine should have if it's even possible to balance them.
If it's impossible to balance them (total dresses cannot be evenly divided), then there's no solution, so stop.
Start by trying a single move: move one dress from one machine to another. Record the number of moves.
Keep moving dresses one by one between machines in all possible ways.
After each move, check if all machines have the same number of dresses.
If they do, we have a balanced state, and we note down the total number of moves it took to reach that state.
If we explore all possible moves up to a certain reasonable limit and haven't found a balanced state, assume there's no solution within that limit.
Once we have tried all valid combinations of moves (or reached the limit), find the smallest number of moves it took to reach a balanced state. That's our answer.

Code Implementation

def super_washing_machines_brute_force(machines):
    total_dresses = sum(machines)
    number_of_machines = len(machines)

    # If the dresses can't be evenly distributed, it's impossible
    if total_dresses % number_of_machines != 0:
        return -1

    average_dresses = total_dresses // number_of_machines
    min_moves = float('inf')

    def solve(current_machines, moves):
        nonlocal min_moves

        all_equal = all(machine == average_dresses for machine in current_machines)
        if all_equal:
            min_moves = min(min_moves, moves)
            return

        # Limit the search depth to avoid infinite loops
        if moves > 10 * number_of_machines:
            return

        for i in range(number_of_machines):
            if current_machines[i] != average_dresses:
                for j in range(number_of_machines):
                    if i != j:
                        # Try moving a dress from i to j
                        temp_machines = current_machines[:]
                        if current_machines[i] > 0:
                            temp_machines[i] -= 1
                            temp_machines[j] += 1

                            # Recursively solve with the new state
                            solve(temp_machines, moves + 1)

    # Start the search from the initial state with 0 moves
    solve(machines, 0)

    # If no solution was found, return -1
    if min_moves == float('inf'):
        return -1
    else:
        return min_moves

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(unbounded) – The brute force approach explores all possible distributions of dresses between washing machines by simulating dress movements one at a time. The algorithm iterates through every machine and considers all possible moves to other machines, repeatedly. In the worst-case scenario, especially if the total number of dresses is significantly unevenly distributed initially, the number of possible move combinations to explore grows exponentially with the number of machines (n) and the number of dresses, and the arbitrary limit on moves doesn't allow an accurate calculation of the number of operations. Hence the time complexity can be considered as unbounded within realistic limits since there are very loosely defined bounds on the depth of exploration, thus making it effectively unpredictable and not representable by a simple polynomial.

Space Complexity

O(N^N) – The brute force method described explores all possible ways to redistribute dresses. In the worst-case scenario, we might need to store the state of the machines after each move to track the number of moves to reach a balanced state. Since each machine could potentially have its dress count changed in each move, and we are exploring 'all possible moves', we need to keep track of the machine states. Therefore the space needed to store the intermediate states could grow exponentially with the input size, where N is the number of washing machines. To exhaustively try all moves, the number of states that may need to be stored grows as N^N representing the number of redistributions and each state requiring N spaces for the machine list.

Optimal Solution

Approach

The problem can be viewed as balancing out the load between washing machines. We aim to determine the minimum number of moves required to achieve an equal distribution of dresses among all machines by transferring dresses between adjacent machines.

Here's how the algorithm would work step-by-step:

First, calculate the total number of dresses and the number of machines, then compute the average number of dresses per machine.
If the total number of dresses can't be evenly divided by the number of machines, there's no way to balance the load, so the answer is 'impossible'.
Imagine each machine has a 'debt' or 'surplus', representing the difference between its number of dresses and the average number. A positive number means it needs to send out dresses, and a negative number means it needs to receive dresses.
Go through the machines from left to right, keeping track of a cumulative 'transfer amount'. This represents the net flow of dresses that needs to pass through the current machine.
At each machine, determine the absolute value of the transfer amount. This tells us the minimum number of moves that have to happen *through* this machine to balance the load on one side or the other.
The number of moves needed at a machine is also influenced by its own 'debt' or 'surplus'. If a machine needs to send dresses both to its left and right, the number of moves will be the sum of these outwards flows.
The maximum of the transfer amount and the individual machine's need will represent the moves required for this position.
The overall minimum number of moves needed to balance all washing machines will be the largest of all calculated local maximums.

Code Implementation

def super_washing_machines(machines):
    number_of_machines = len(machines)
    total_dresses = sum(machines)

    average_dresses = total_dresses / number_of_machines

    # Impossible to balance if total dresses can't be evenly divided
    if total_dresses % number_of_machines != 0:
        return -1

    max_moves = 0
    transfer_amount = 0

    for dresses_at_machine in machines:
        # Calculate the difference between current and target
        difference = dresses_at_machine - average_dresses

        # Update the cumulative transfer amount
        transfer_amount += difference

        # The number of moves depends on both transfer and difference
        moves_needed = max(abs(transfer_amount), difference)

        # Track the global maximum moves needed
        max_moves = max(max_moves, abs(moves_needed))

    return int(max_moves)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the input array of washing machines once. The calculation of the total dresses, average dresses, and the cumulative transfer amount all take place within a single loop that visits each machine. Therefore, the time complexity is directly proportional to the number of machines, n, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it primarily uses a few integer variables to store the total dresses, average dresses per machine, the current transfer amount, and the maximum number of moves needed. No auxiliary data structures like arrays or hash maps are created that scale with the input size (number of machines). Therefore, the space used remains constant regardless of the input size N (number of washing machines).

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no machines and thus no moves are needed.
Array with one washing machine	Return 0 because a single machine is already balanced.
Array with all identical values	Return 0, as the machines are already balanced and no moves are needed.
Total number of dresses not evenly divisible by the number of washing machines	Return -1 because it's impossible to balance the dresses among the machines.
Integer overflow when calculating the total number of dresses	Use a data type that can hold the total number of dresses (e.g., long) or check for potential overflow before summing.
Large array size impacting memory or performance	The algorithm should be O(n), so it should scale linearly, but memory consumption should be monitored for very large n.
Highly skewed distribution of dresses (one machine with a huge number)	The algorithm should correctly handle skewed distributions as it focuses on the imbalances between machines and the average.
The algorithm gets stuck in an infinite loop when balancing	The algorithm calculates the max load required from each machine to other machines to achieve average dresses in the end so that the algorithm always converges.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the number of dresses in each washing machine? Can a washing machine have a negative number of dresses?
Can the input array `machines` be empty or null? What should the output be in such cases?
If it's impossible to equalize the dresses in all machines, what value should I return? (e.g., -1, null, throw an exception)?
Is the number of washing machines guaranteed to be within a reasonable range (e.g., less than 10,000)? This might affect memory usage and algorithm choice.
Does the array `machines` only contain integers, or could there be floating-point values?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the average number of dresses each machine should have if it's even possible to balance them.
If it's impossible to balance them (total dresses cannot be evenly divided), then there's no solution, so stop.
Start by trying a single move: move one dress from one machine to another. Record the number of moves.
Keep moving dresses one by one between machines in all possible ways.
After each move, check if all machines have the same number of dresses.
If they do, we have a balanced state, and we note down the total number of moves it took to reach that state.
If we explore all possible moves up to a certain reasonable limit and haven't found a balanced state, assume there's no solution within that limit.
Once we have tried all valid combinations of moves (or reached the limit), find the smallest number of moves it took to reach a balanced state. That's our answer.

Code Implementation

def super_washing_machines_brute_force(machines):
    total_dresses = sum(machines)
    number_of_machines = len(machines)

    # If the dresses can't be evenly distributed, it's impossible
    if total_dresses % number_of_machines != 0:
        return -1

    average_dresses = total_dresses // number_of_machines
    min_moves = float('inf')

    def solve(current_machines, moves):
        nonlocal min_moves

        all_equal = all(machine == average_dresses for machine in current_machines)
        if all_equal:
            min_moves = min(min_moves, moves)
            return

        # Limit the search depth to avoid infinite loops
        if moves > 10 * number_of_machines:
            return

        for i in range(number_of_machines):
            if current_machines[i] != average_dresses:
                for j in range(number_of_machines):
                    if i != j:
                        # Try moving a dress from i to j
                        temp_machines = current_machines[:]
                        if current_machines[i] > 0:
                            temp_machines[i] -= 1
                            temp_machines[j] += 1

                            # Recursively solve with the new state
                            solve(temp_machines, moves + 1)

    # Start the search from the initial state with 0 moves
    solve(machines, 0)

    # If no solution was found, return -1
    if min_moves == float('inf'):
        return -1
    else:
        return min_moves

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the total number of dresses and the number of machines, then compute the average number of dresses per machine.
If the total number of dresses can't be evenly divided by the number of machines, there's no way to balance the load, so the answer is 'impossible'.
Imagine each machine has a 'debt' or 'surplus', representing the difference between its number of dresses and the average number. A positive number means it needs to send out dresses, and a negative number means it needs to receive dresses.
Go through the machines from left to right, keeping track of a cumulative 'transfer amount'. This represents the net flow of dresses that needs to pass through the current machine.
At each machine, determine the absolute value of the transfer amount. This tells us the minimum number of moves that have to happen *through* this machine to balance the load on one side or the other.
The number of moves needed at a machine is also influenced by its own 'debt' or 'surplus'. If a machine needs to send dresses both to its left and right, the number of moves will be the sum of these outwards flows.
The maximum of the transfer amount and the individual machine's need will represent the moves required for this position.
The overall minimum number of moves needed to balance all washing machines will be the largest of all calculated local maximums.

Code Implementation

def super_washing_machines(machines):
    number_of_machines = len(machines)
    total_dresses = sum(machines)

    average_dresses = total_dresses / number_of_machines

    # Impossible to balance if total dresses can't be evenly divided
    if total_dresses % number_of_machines != 0:
        return -1

    max_moves = 0
    transfer_amount = 0

    for dresses_at_machine in machines:
        # Calculate the difference between current and target
        difference = dresses_at_machine - average_dresses

        # Update the cumulative transfer amount
        transfer_amount += difference

        # The number of moves depends on both transfer and difference
        moves_needed = max(abs(transfer_amount), difference)

        # Track the global maximum moves needed
        max_moves = max(max_moves, abs(moves_needed))

    return int(max_moves)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no machines and thus no moves are needed.
Array with one washing machine	Return 0 because a single machine is already balanced.
Array with all identical values	Return 0, as the machines are already balanced and no moves are needed.
Total number of dresses not evenly divisible by the number of washing machines	Return -1 because it's impossible to balance the dresses among the machines.
Integer overflow when calculating the total number of dresses	Use a data type that can hold the total number of dresses (e.g., long) or check for potential overflow before summing.
Large array size impacting memory or performance	The algorithm should be O(n), so it should scale linearly, but memory consumption should be monitored for very large n.
Highly skewed distribution of dresses (one machine with a huge number)	The algorithm should correctly handle skewed distributions as it focuses on the imbalances between machines and the average.
The algorithm gets stuck in an infinite loop when balancing	The algorithm calculates the max load required from each machine to other machines to achieve average dresses in the end so that the algorithm always converges.