Jobs

Interviews

Discussions

Sorting Three Groups

Medium

UiPath

1 view

Topics:

ArraysDynamic Programming

You are given an integer array nums. Each element in nums is 1, 2 or 3. In each operation, you can remove an element from nums. Return the minimum number of operations to make nums non-decreasing.

Example 1:

Input: nums = [2,1,3,2,1]

Output: 3

Explanation:

One of the optimal solutions is to remove nums[0], nums[2] and nums[3].

Example 2:

Input: nums = [1,3,2,1,3,3]

Output: 2

Explanation:

One of the optimal solutions is to remove nums[1] and nums[2].

Example 3:

Input: nums = [2,2,2,2,3,3]

Output: 0

Explanation:

nums is already non-decreasing.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 3

Follow-up: Can you come up with an algorithm that runs in O(n) time complexity?

Try coding it in LeetCode

Sorting Three Groups

Medium

UiPath

1 view

Topics:

ArraysDynamic Programming

Example 1:

Input: nums = [2,1,3,2,1]

Output: 3

Explanation:

One of the optimal solutions is to remove nums[0], nums[2] and nums[3].

Example 2:

Input: nums = [1,3,2,1,3,3]

Output: 2

Explanation:

One of the optimal solutions is to remove nums[1] and nums[2].

Example 3:

Input: nums = [2,2,2,2,3,3]

Output: 0

Explanation:

nums is already non-decreasing.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 3

Follow-up: Can you come up with an algorithm that runs in O(n) time complexity?

Try coding it in LeetCode

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 maximum size of the input array `nums`?
Is the input array guaranteed to contain only the numbers 1, 2, and 3, or could it contain other integers?
If the input array is already sorted, should I return 0?
Can I modify the input array directly?
Are the integers represented as primitive int or Integer objects?

Brute Force Solution

Approach

The brute force approach for sorting three groups involves checking every single possible arrangement. We consider each item and try putting it into each of the three groups, one at a time, until we find a valid solution. This is like trying every combination until we find the right one.

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

Take the first item.
Try putting it in the first group.
Then try putting it in the second group.
Finally, try putting it in the third group.
Now, take the second item and repeat the process of trying it in each of the three groups for each of the placements of the first item we already tried.
Continue this process for all the items. This generates all possible combinations of items in the three groups.
For each complete arrangement, check if it meets the sorting criteria for the groups. For example, is everything in group one smaller than everything in group two, and so on.
If the arrangement meets the criteria, save it as a potential solution.
After checking all possible arrangements, compare all the saved solutions and pick the best one according to the specific rules of the sorting problem (e.g., minimizing the number of items out of place).

Code Implementation

def sort_three_groups_brute_force(items):    number_of_items = len(items)
    best_arrangement = None
    
    def generate_arrangements(index, current_arrangement):
        nonlocal best_arrangement

        if index == number_of_items:
            # Check if the current arrangement is valid
            if is_valid_arrangement(current_arrangement, items):
                if best_arrangement is None or is_better_arrangement(current_arrangement, best_arrangement, items):
                    best_arrangement = current_arrangement[:]
            return

        for group_number in range(3):
            current_arrangement.append(group_number)
            generate_arrangements(index + 1, current_arrangement)
            current_arrangement.pop()

    def is_valid_arrangement(arrangement, items):
        group_one = []
        group_two = []
        group_three = []

        for index, group_number in enumerate(arrangement):
            if group_number == 0:
                group_one.append(items[index])
            elif group_number == 1:
                group_two.append(items[index])
            else:
                group_three.append(items[index])

        if not group_one and not group_two and not group_three:
            return True

        # Check if group one is smaller than group two and three
        if group_one and group_two and max(group_one) > min(group_two):
            return False
        if group_one and group_three and max(group_one) > min(group_three):
            return False

        # Check if group two is smaller than group three
        if group_two and group_three and max(group_two) > min(group_three):
            return False

        return True

    def is_better_arrangement(arrangement_one, arrangement_two, items):
        # Counting misplaced items in each arrangement
        misplaced_one = count_misplaced_items(arrangement_one, items)
        misplaced_two = count_misplaced_items(arrangement_two, items)

        #Prioritize an arrangement with fewer misplaced items.
        return misplaced_one < misplaced_two

    def count_misplaced_items(arrangement, items):
        misplaced_count = 0
        for index, group_number in enumerate(arrangement):
            if group_number != get_ideal_group(items[index]):
                misplaced_count += 1
        return misplaced_count

    def get_ideal_group(item):
        # A placeholder logic, assuming the ideal group can be determined from the item's value.
        if item < 3:
            return 0
        elif item < 7:
            return 1
        else:
            return 2

    # Start generating arrangements from the first item.
    generate_arrangements(0, [])

    return best_arrangement

Big(O) Analysis

Time Complexity

O(3^n * n) – The algorithm considers each of the n items and tries placing it into one of the three groups. This generates 3 possible placements for each item, leading to 3*3*...*3 (n times) or 3^n possible arrangements. For each of these arrangements, we need to check if the sorting criteria are met which requires examining all n elements to ensure correct group ordering. Therefore, the time complexity is proportional to 3^n multiplied by n, resulting in O(3^n * n).

Space Complexity

O(3^N) – The brute force approach explores all possible arrangements of N items into three groups. Each item can be placed in one of three groups, leading to a branching factor of 3 at each of the N steps. This generates a recursion tree with a depth of N, where N is the number of items to sort, and each node represents a partial arrangement. The space complexity is dominated by the storage of these partial arrangements (the recursion stack). Therefore, the space complexity is O(3^N).

Optimal Solution

Approach

The best way to sort three groups is to think about it like moving items to their correct positions in a line. We want to minimize the number of moves by focusing on placing things where they belong, rather than shuffling everything randomly.

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

Imagine you have three types of objects (let's say red, white, and blue) all mixed up in a single line.
Think of the line as having three sections: one for all the reds, one for all the whites, and one for all the blues.
Start by looking at each object in the line, one at a time, from left to right.
If you find a red object in the wrong section (not in the red section), swap it with an object in the red section that's in the wrong place.
Do the same for the white objects, making sure they are in the white section. Be careful not to move a red object you already put in place!
After you've placed the red and white objects correctly, all the blue objects will automatically be in the correct place. You don't need to do anything special for them.

Code Implementation

def sort_three_groups(data):
    first_group_index = 0
    second_group_index = 0

    # Move all first group elements to the beginning.
    for i in range(len(data)):
        if data[i] == 0:
            data[i], data[first_group_index] = data[first_group_index], data[i]
            first_group_index += 1

    # Move all second group elements after the first group.
    for i in range(first_group_index, len(data)): 
        if data[i] == 1:
            # Find the next available spot for second group
            data[i], data[second_group_index + first_group_index] = data[second_group_index + first_group_index], data[i]
            second_group_index += 1

    return data

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n, checking each element's position. For each element, it potentially searches for elements of a different type to swap with, which in the worst case requires another iteration within the unsorted portion of the array. This nested iteration results in approximately n * (average search length) operations. Since the average search length can be proportional to n in the worst-case, the total number of operations approximates n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm operates in place, modifying the input array directly. It only requires a constant number of integer variables for tracking indices or performing swaps, regardless of the size of the input array. Therefore, the auxiliary space used is independent of the input size N. The space complexity is O(1), indicating constant extra space.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately since no swaps are needed for an empty or null array.
Array with only one element	Return 0 immediately since a single-element array is already sorted.
Array with all elements being the same value (e.g., all 1s)	Return 0 immediately since no swaps are needed for an array with identical elements.
Array already sorted in non-decreasing order	Return 0 immediately since no swaps are needed for an already sorted array.
Large input array to test for performance	The solution's O(n) complexity should handle large arrays efficiently, but consider memory usage.
Integer overflow when calculating counts (unlikely with only 1, 2, or 3, but consider in other sorting problems)	Using appropriate data types (e.g., long) for counts will avoid potential integer overflow issues.
Array with a highly skewed distribution (e.g., mostly 1s and very few 2s and 3s)	The algorithm will correctly identify and swap the misplaced elements regardless of the distribution.
Invalid input values (other than 1, 2, or 3)	Add validation to check if all elements are 1, 2, or 3 and throw an exception or return an error code if not.

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 maximum size of the input array `nums`?
Is the input array guaranteed to contain only the numbers 1, 2, and 3, or could it contain other integers?
If the input array is already sorted, should I return 0?
Can I modify the input array directly?
Are the integers represented as primitive int or Integer objects?

Brute Force Solution

Approach

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

Take the first item.
Try putting it in the first group.
Then try putting it in the second group.
Finally, try putting it in the third group.
Now, take the second item and repeat the process of trying it in each of the three groups for each of the placements of the first item we already tried.
Continue this process for all the items. This generates all possible combinations of items in the three groups.
For each complete arrangement, check if it meets the sorting criteria for the groups. For example, is everything in group one smaller than everything in group two, and so on.
If the arrangement meets the criteria, save it as a potential solution.
After checking all possible arrangements, compare all the saved solutions and pick the best one according to the specific rules of the sorting problem (e.g., minimizing the number of items out of place).

Code Implementation

def sort_three_groups_brute_force(items):    number_of_items = len(items)
    best_arrangement = None
    
    def generate_arrangements(index, current_arrangement):
        nonlocal best_arrangement

        if index == number_of_items:
            # Check if the current arrangement is valid
            if is_valid_arrangement(current_arrangement, items):
                if best_arrangement is None or is_better_arrangement(current_arrangement, best_arrangement, items):
                    best_arrangement = current_arrangement[:]
            return

        for group_number in range(3):
            current_arrangement.append(group_number)
            generate_arrangements(index + 1, current_arrangement)
            current_arrangement.pop()

    def is_valid_arrangement(arrangement, items):
        group_one = []
        group_two = []
        group_three = []

        for index, group_number in enumerate(arrangement):
            if group_number == 0:
                group_one.append(items[index])
            elif group_number == 1:
                group_two.append(items[index])
            else:
                group_three.append(items[index])

        if not group_one and not group_two and not group_three:
            return True

        # Check if group one is smaller than group two and three
        if group_one and group_two and max(group_one) > min(group_two):
            return False
        if group_one and group_three and max(group_one) > min(group_three):
            return False

        # Check if group two is smaller than group three
        if group_two and group_three and max(group_two) > min(group_three):
            return False

        return True

    def is_better_arrangement(arrangement_one, arrangement_two, items):
        # Counting misplaced items in each arrangement
        misplaced_one = count_misplaced_items(arrangement_one, items)
        misplaced_two = count_misplaced_items(arrangement_two, items)

        #Prioritize an arrangement with fewer misplaced items.
        return misplaced_one < misplaced_two

    def count_misplaced_items(arrangement, items):
        misplaced_count = 0
        for index, group_number in enumerate(arrangement):
            if group_number != get_ideal_group(items[index]):
                misplaced_count += 1
        return misplaced_count

    def get_ideal_group(item):
        # A placeholder logic, assuming the ideal group can be determined from the item's value.
        if item < 3:
            return 0
        elif item < 7:
            return 1
        else:
            return 2

    # Start generating arrangements from the first item.
    generate_arrangements(0, [])

    return best_arrangement

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have three types of objects (let's say red, white, and blue) all mixed up in a single line.
Think of the line as having three sections: one for all the reds, one for all the whites, and one for all the blues.
Start by looking at each object in the line, one at a time, from left to right.
If you find a red object in the wrong section (not in the red section), swap it with an object in the red section that's in the wrong place.
Do the same for the white objects, making sure they are in the white section. Be careful not to move a red object you already put in place!
After you've placed the red and white objects correctly, all the blue objects will automatically be in the correct place. You don't need to do anything special for them.

Code Implementation

def sort_three_groups(data):
    first_group_index = 0
    second_group_index = 0

    # Move all first group elements to the beginning.
    for i in range(len(data)):
        if data[i] == 0:
            data[i], data[first_group_index] = data[first_group_index], data[i]
            first_group_index += 1

    # Move all second group elements after the first group.
    for i in range(first_group_index, len(data)): 
        if data[i] == 1:
            # Find the next available spot for second group
            data[i], data[second_group_index + first_group_index] = data[second_group_index + first_group_index], data[i]
            second_group_index += 1

    return data

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately since no swaps are needed for an empty or null array.
Array with only one element	Return 0 immediately since a single-element array is already sorted.
Array with all elements being the same value (e.g., all 1s)	Return 0 immediately since no swaps are needed for an array with identical elements.
Array already sorted in non-decreasing order	Return 0 immediately since no swaps are needed for an already sorted array.
Large input array to test for performance	The solution's O(n) complexity should handle large arrays efficiently, but consider memory usage.
Integer overflow when calculating counts (unlikely with only 1, 2, or 3, but consider in other sorting problems)	Using appropriate data types (e.g., long) for counts will avoid potential integer overflow issues.
Array with a highly skewed distribution (e.g., mostly 1s and very few 2s and 3s)	The algorithm will correctly identify and swap the misplaced elements regardless of the distribution.
Invalid input values (other than 1, 2, or 3)	Add validation to check if all elements are 1, 2, or 3 and throw an exception or return an error code if not.