Jobs

Interviews

Discussions

Minimum Swaps To Make Sequences Increasing

Hard

Minimum Swaps To Make Sequences Increasing

Hard

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 are the possible ranges and data types of the numbers in `nums1` and `nums2`? Can they be negative or zero?
Are `nums1` and `nums2` guaranteed to have the same length, and will that length always be greater than zero?
If it's impossible to make both sequences strictly increasing with any number of swaps, what value should I return?
If there are multiple sequences of swaps that result in the minimum number of swaps, is any one of those sequences acceptable?
Could you provide a more concrete example to illustrate the problem and expected output in a less ambiguous way?

Brute Force Solution

Approach

The brute-force approach involves trying every possible combination of swaps to find the one that makes both sequences strictly increasing. We essentially explore all possible swap/no-swap decisions at each position. This will guarantee we find the absolute minimum number of swaps, at the cost of exploring many unnecessary options.

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

Start at the beginning of the sequences.
At each position, we have two choices: either swap the numbers at that position between the two sequences, or don't swap them.
Consider the possibility of swapping the numbers at the current position.
Check if the swap makes the sequences strictly increasing up to this point. If it doesn't, this is not a valid path.
Consider the possibility of not swapping the numbers at the current position.
Check if not swapping makes the sequences strictly increasing up to this point. If it doesn't, this is not a valid path.
If either the swap or no-swap option makes the sequences strictly increasing, continue to the next position, remembering the number of swaps we've made.
Repeat steps 2-7 for every position in the sequences, exploring all possible combinations of swaps.
Once we reach the end of the sequences, we have a possible solution. Record the number of swaps used in this solution.
Repeat the entire process, exploring all other possible combinations of swaps.
After exploring all possible combinations, compare the number of swaps used in each valid solution.
Choose the solution with the smallest number of swaps. This is the minimum number of swaps required.

Code Implementation

def min_swap_brute_force(first_array, second_array):
    minimum_swaps = float('inf')

    def is_strictly_increasing(array):
        for index in range(1, len(array)):
            if array[index] <= array[index - 1]:
                return False
        return True

    def explore_swaps(current_index, swaps_so_far):
        nonlocal minimum_swaps

        if current_index == len(first_array):
            # We have reached the end of the arrays, check the swaps so far
            if is_strictly_increasing(first_array) and is_strictly_increasing(second_array):
                minimum_swaps = min(minimum_swaps, swaps_so_far)
            return

        # Option 1: Don't swap the current elements
        original_first = first_array[current_index]
        original_second = second_array[current_index]

        if current_index == 0 or (first_array[current_index] > first_array[current_index - 1] and second_array[current_index] > second_array[current_index - 1]):
            explore_swaps(current_index + 1, swaps_so_far)

        # Option 2: Swap the current elements
        first_array[current_index], second_array[current_index] = second_array[current_index], first_array[current_index]

        # After swapping, check if it leads to valid strictly increasing sequences
        if current_index == 0 or (first_array[current_index] > first_array[current_index - 1] and second_array[current_index] > second_array[current_index - 1]):
            # If the sequence is strictly increasing, recurse.
            explore_swaps(current_index + 1, swaps_so_far + 1)

        # Backtrack: Restore the original arrays for exploring other possibilities
        first_array[current_index] = original_first
        second_array[current_index] = original_second

    explore_swaps(0, 0)
    return minimum_swaps

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations of swaps at each position in the input arrays. For each of the n positions, we have two choices: either swap or don't swap. This branching creates a binary tree of possibilities. Therefore, the number of possible combinations grows exponentially with the size of the input, resulting in 2^n possible paths to explore. Each path involves checking if the sequences are increasing, but the dominating factor is the sheer number of paths. Thus, the time complexity is O(2^n).

Space Complexity

O(2^N) – The brute-force approach explores all possible combinations of swaps. The core driver of space complexity is the implicit recursion stack. At each position in the sequence of length N, we have two choices (swap or no-swap), leading to a branching factor of 2. Therefore, the maximum depth of the recursion can be N, and in the worst-case scenario where all paths are explored the call stack can have a maximum depth of N, and each call stack will have two choices at each position, so the auxiliary space needed to keep track of these calls sums up to a space complexity of O(2^N).

Optimal Solution

Approach

The most efficient strategy is to figure out what decision we have to make at each step, and then choose the best decision to minimize total switches. The key idea is that at each position, we can either switch both numbers at that position or not switch them, so we only need to keep track of the best way to achieve both of those states.

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

Consider each pair of numbers at the same position in the two number sets.
We need to decide if we should switch both numbers in that pair or leave them as they are.
Keep track of the fewest switches needed to make the number sets increasing up to that point, both when we switch the current numbers and when we don't.
To figure this out, we look at the previous pair. If the previous pair could have been left unchanged, consider what happens if you switch the current pair or don't switch them. Same if the previous pair was switched. Check both cases.
Make sure that the new numbers you arrive at are actually higher than the numbers you are comparing to. Otherwise, that path is not valid.
Decide whether switching or not switching at the current position gives us the smallest number of switches so far.
After going through all the number pairs, the smaller of the final switch and non-switch counts tells you the fewest switches needed to make the number sets increase.

Code Implementation

def minimum_swaps_to_make_sequences_increasing(first_array, second_array): 
    number_of_elements = len(first_array)
    do_not_swap_count = [0] * number_of_elements
    swap_count = [0] * number_of_elements

    swap_count[0] = 1

    for i in range(1, number_of_elements):
        do_not_swap_count[i] = float('inf')
        swap_count[i] = float('inf')

        # Previous was not swapped
        if first_array[i] > first_array[i-1] and second_array[i] > second_array[i-1]:
            do_not_swap_count[i] = do_not_swap_count[i-1]
            swap_count[i] = swap_count[i-1] + 1

        # Previous was swapped
        if first_array[i] > second_array[i-1] and second_array[i] > first_array[i-1]:
            do_not_swap_count[i] = min(do_not_swap_count[i], swap_count[i-1])
            swap_count[i] = min(swap_count[i], do_not_swap_count[i-1] + 1)

    # Determine the minimum swaps after considering all elements
    return min(do_not_swap_count[number_of_elements-1], swap_count[number_of_elements-1])

Big(O) Analysis

Time Complexity

O(n) – The described algorithm iterates through the input sequences of length n, examining each pair of numbers at the same position exactly once. At each position, it performs a fixed number of comparisons and calculations to determine the minimum switches needed, independent of the input size. Therefore, the time complexity is directly proportional to the number of pairs (n), resulting in O(n).

Space Complexity

O(1) – The algorithm keeps track of the minimum switches needed to make the sequences increasing up to the current position, both when the current numbers are switched and when they are not. This is done using a constant number of variables to store the switch and non-switch counts. Therefore, the auxiliary space required does not depend on the input size N (where N is the length of the input arrays) and remains constant.

Edge Cases

Case	How to Handle
Empty input arrays A or B	Return 0 swaps immediately as no operation is needed.
Arrays A and B have only 2 elements	Check if A[0] < A[1] and B[0] < B[1]; if not, perform one swap if necessary and possible.
Arrays A and B are already strictly increasing with no swaps	The dynamic programming approach correctly determines and returns the minimum swaps (0).
Arrays A and B are of maximum size (e.g., 10^5 elements) and carefully designed to require either many swaps, or none	Ensure that the solution uses O(N) space and time for dynamic programming to remain efficient.
The input arrays are crafted to maximize the recursion depth, potentially causing stack overflow errors if a naive recursive approach is used.	Use dynamic programming instead of recursion to avoid stack overflow issues, iterating instead.
Cases where it is impossible to make both sequences strictly increasing, such as overlapping ranges within arrays after a swap.	The dynamic programming approach will identify infeasible paths, eventually reaching a point where no minimum swap count can be determined.
Integer overflow when calculating intermediate swap counts if the numbers are huge	Use a sufficiently large data type (e.g., long) to store swap counts and intermediate values.
Values in arrays A and B are negative, zero, or large positive values	The comparison operations (A[i] > A[i-1], B[i] > B[i-1]) work correctly regardless of the sign or magnitude of the array values.

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 are the possible ranges and data types of the numbers in `nums1` and `nums2`? Can they be negative or zero?
Are `nums1` and `nums2` guaranteed to have the same length, and will that length always be greater than zero?
If it's impossible to make both sequences strictly increasing with any number of swaps, what value should I return?
If there are multiple sequences of swaps that result in the minimum number of swaps, is any one of those sequences acceptable?
Could you provide a more concrete example to illustrate the problem and expected output in a less ambiguous way?

Brute Force Solution

Approach

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

Start at the beginning of the sequences.
At each position, we have two choices: either swap the numbers at that position between the two sequences, or don't swap them.
Consider the possibility of swapping the numbers at the current position.
Check if the swap makes the sequences strictly increasing up to this point. If it doesn't, this is not a valid path.
Consider the possibility of not swapping the numbers at the current position.
Check if not swapping makes the sequences strictly increasing up to this point. If it doesn't, this is not a valid path.
If either the swap or no-swap option makes the sequences strictly increasing, continue to the next position, remembering the number of swaps we've made.
Repeat steps 2-7 for every position in the sequences, exploring all possible combinations of swaps.
Once we reach the end of the sequences, we have a possible solution. Record the number of swaps used in this solution.
Repeat the entire process, exploring all other possible combinations of swaps.
After exploring all possible combinations, compare the number of swaps used in each valid solution.
Choose the solution with the smallest number of swaps. This is the minimum number of swaps required.

Code Implementation

def min_swap_brute_force(first_array, second_array):
    minimum_swaps = float('inf')

    def is_strictly_increasing(array):
        for index in range(1, len(array)):
            if array[index] <= array[index - 1]:
                return False
        return True

    def explore_swaps(current_index, swaps_so_far):
        nonlocal minimum_swaps

        if current_index == len(first_array):
            # We have reached the end of the arrays, check the swaps so far
            if is_strictly_increasing(first_array) and is_strictly_increasing(second_array):
                minimum_swaps = min(minimum_swaps, swaps_so_far)
            return

        # Option 1: Don't swap the current elements
        original_first = first_array[current_index]
        original_second = second_array[current_index]

        if current_index == 0 or (first_array[current_index] > first_array[current_index - 1] and second_array[current_index] > second_array[current_index - 1]):
            explore_swaps(current_index + 1, swaps_so_far)

        # Option 2: Swap the current elements
        first_array[current_index], second_array[current_index] = second_array[current_index], first_array[current_index]

        # After swapping, check if it leads to valid strictly increasing sequences
        if current_index == 0 or (first_array[current_index] > first_array[current_index - 1] and second_array[current_index] > second_array[current_index - 1]):
            # If the sequence is strictly increasing, recurse.
            explore_swaps(current_index + 1, swaps_so_far + 1)

        # Backtrack: Restore the original arrays for exploring other possibilities
        first_array[current_index] = original_first
        second_array[current_index] = original_second

    explore_swaps(0, 0)
    return minimum_swaps

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Consider each pair of numbers at the same position in the two number sets.
We need to decide if we should switch both numbers in that pair or leave them as they are.
Keep track of the fewest switches needed to make the number sets increasing up to that point, both when we switch the current numbers and when we don't.
To figure this out, we look at the previous pair. If the previous pair could have been left unchanged, consider what happens if you switch the current pair or don't switch them. Same if the previous pair was switched. Check both cases.
Make sure that the new numbers you arrive at are actually higher than the numbers you are comparing to. Otherwise, that path is not valid.
Decide whether switching or not switching at the current position gives us the smallest number of switches so far.
After going through all the number pairs, the smaller of the final switch and non-switch counts tells you the fewest switches needed to make the number sets increase.

Code Implementation

def minimum_swaps_to_make_sequences_increasing(first_array, second_array): 
    number_of_elements = len(first_array)
    do_not_swap_count = [0] * number_of_elements
    swap_count = [0] * number_of_elements

    swap_count[0] = 1

    for i in range(1, number_of_elements):
        do_not_swap_count[i] = float('inf')
        swap_count[i] = float('inf')

        # Previous was not swapped
        if first_array[i] > first_array[i-1] and second_array[i] > second_array[i-1]:
            do_not_swap_count[i] = do_not_swap_count[i-1]
            swap_count[i] = swap_count[i-1] + 1

        # Previous was swapped
        if first_array[i] > second_array[i-1] and second_array[i] > first_array[i-1]:
            do_not_swap_count[i] = min(do_not_swap_count[i], swap_count[i-1])
            swap_count[i] = min(swap_count[i], do_not_swap_count[i-1] + 1)

    # Determine the minimum swaps after considering all elements
    return min(do_not_swap_count[number_of_elements-1], swap_count[number_of_elements-1])

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input arrays A or B	Return 0 swaps immediately as no operation is needed.
Arrays A and B have only 2 elements	Check if A[0] < A[1] and B[0] < B[1]; if not, perform one swap if necessary and possible.
Arrays A and B are already strictly increasing with no swaps	The dynamic programming approach correctly determines and returns the minimum swaps (0).
Arrays A and B are of maximum size (e.g., 10^5 elements) and carefully designed to require either many swaps, or none	Ensure that the solution uses O(N) space and time for dynamic programming to remain efficient.
The input arrays are crafted to maximize the recursion depth, potentially causing stack overflow errors if a naive recursive approach is used.	Use dynamic programming instead of recursion to avoid stack overflow issues, iterating instead.
Cases where it is impossible to make both sequences strictly increasing, such as overlapping ranges within arrays after a swap.	The dynamic programming approach will identify infeasible paths, eventually reaching a point where no minimum swap count can be determined.
Integer overflow when calculating intermediate swap counts if the numbers are huge	Use a sufficiently large data type (e.g., long) to store swap counts and intermediate values.
Values in arrays A and B are negative, zero, or large positive values	The comparison operations (A[i] > A[i-1], B[i] > B[i-1]) work correctly regardless of the sign or magnitude of the array values.