Jobs

Interviews

Discussions

Partition List

Medium

Asked by:

More companies

38 views

Topics:

Linked ListsTwo Pointers

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Try coding it in LeetCode

Partition List

Medium

Asked by:

38 views

Topics:

Linked ListsTwo Pointers

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

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 data type of the list elements and the partition value 'x'? Are they integers, floats, or something else?
Can the input list be empty or null? What should I return in those cases?
If a node's value is equal to 'x', where should it be placed in the partitioned list: before or after the group of nodes less than 'x'?
Does the relative order of nodes within each partition (less than x and greater than or equal to x) need to be preserved?
Is it guaranteed that 'x' will be present in the list? If not, how should I handle that scenario?

Brute Force Solution

Approach

The goal is to rearrange a linked list so that all values less than a given number come before all values greater than or equal to it. A brute force method involves creating two separate temporary storage areas. We then place the elements accordingly and combine them.

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

Create one storage area to temporarily hold all values from the original list that are less than the given number.
Create another separate storage area to hold all the other values (those greater than or equal to the given number).
Go through the original list, one value at a time.
If a value is less than the given number, put it into the first storage area.
Otherwise, put the value into the second storage area.
Once we've moved all the values from the original list, take all the values from the first storage area and put them back into a new linked list.
Then, take all the values from the second storage area and add them to the end of that new linked list.
The resulting linked list is the rearranged list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def partition_list_brute_force(head, partition_value):
    less_than_partition = []
    greater_equal_partition = []

    current_node = head
    while current_node:
        # Append values to respective lists based on comparison.
        if current_node.val < partition_value:
            less_than_partition.append(current_node.val)

        else:
            greater_equal_partition.append(current_node.val)

        current_node = current_node.next

    new_head = None
    tail = None

    # Rebuild linked list using values from less_than_partition.
    for value in less_than_partition:
        new_node = ListNode(value)
        if not new_head:
            new_head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node

    # Append values from greater_equal_partition.
    for value in greater_equal_partition:
        new_node = ListNode(value)
        if not new_head:
            new_head = new_node
            tail = new_node
        else:
            # Only set if there are values in the first list.
            if tail:
                tail.next = new_node
            else:
                new_head = new_node
            tail = new_node

    return new_head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the original linked list once to place each of the n nodes into either the 'less than' or 'greater than or equal to' storage area. After this initial pass, the algorithm iterates through these two storage areas, again processing each of the n nodes exactly once to construct the new linked list. Therefore, the time complexity is dominated by two linear traversals of the n nodes, resulting in O(n).

Space Complexity

O(N) – The described solution utilizes two separate storage areas to hold list node values temporarily. In the worst-case scenario, one storage area might hold all values except one, meaning the sizes of these storage areas could sum up to nearly the size of the original list. Thus, the auxiliary space used grows linearly with the number of nodes, N, in the original list. Therefore the space complexity is O(N).

Optimal Solution

Approach

The goal is to rearrange a linked list so that all the smaller values come before a specific value, and all the larger values come after it, keeping the original order within each group. We do this by creating two separate lists, one for smaller values and one for larger values, and then joining them together.

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

Imagine you have two empty boxes, one for numbers smaller than the target and another for numbers larger than the target.
Go through each number in the original list, one at a time.
If a number is smaller than the target, put it in the 'smaller' box.
If a number is larger than the target, put it in the 'larger' box.
Once you've processed all the numbers, take the 'smaller' box and connect it to the front of the 'larger' box. This combines the two lists in the desired order.

Code Implementation

def partition_list(head, partition_value):
    smaller_head = None
    smaller_tail = None
    larger_head = None
    larger_tail = None

    current_node = head

    while current_node:
        next_node = current_node.next

        if current_node.val < partition_value:
            # Build the list of nodes smaller than the partition value.
            if smaller_head is None:
                smaller_head = current_node
                smaller_tail = current_node
            else:
                smaller_tail.next = current_node
                smaller_tail = current_node
        else:
            # Build the list of nodes larger than or equal to the partition value.
            if larger_head is None:
                larger_head = current_node
                larger_tail = current_node
            else:
                larger_tail.next = current_node
                larger_tail = current_node

        current_node = next_node

    if larger_tail is not None:
        larger_tail.next = None

    # If there are no smaller nodes, return the larger list.
    if smaller_head is None:
        return larger_head

    # Connect the smaller list to the larger list.
    smaller_tail.next = larger_head

    # Return the head of the combined list.
    return smaller_head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once, examining each of the 'n' nodes where 'n' is the number of nodes in the linked list. During each iteration, it performs a constant-time comparison to determine which of the two new lists the current node should be added to. Creating the smaller and larger lists involves simply reassigning pointers as each node is visited. Finally, the concatenation of the two lists is a constant-time operation as it only involves adjusting a few pointers after processing all elements. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(1) – The provided algorithm uses two separate lists to store nodes smaller and larger than the partition value. However, instead of creating new nodes, it rearranges the existing nodes. The plain English explanation only describes using 'boxes' conceptually. No auxiliary data structures with size dependent on the input linked list's size N are actually created. Only a few pointers (variables referencing list nodes) are created to manage the lists, and their count does not depend on N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty list or null input list	Return the original list or null, as there's nothing to partition.
List with only one element	Return the original list, as it's already 'partitioned'.
Partition value is smaller than all elements in the list	All elements should be moved to the 'greater than or equal' partition (right partition), leaving the 'less than' partition empty.
Partition value is larger than all elements in the list	All elements should be moved to the 'less than' partition (left partition), leaving the 'greater than or equal' partition empty.
List contains duplicate values, some smaller and some greater than the partition value	The duplicates should be grouped correctly on either side of the partition according to their value relative to the partition.
List is already partitioned correctly according to the value	The solution should not modify the list in any way and should return it directly.
List contains negative numbers, zeros, and positive numbers	The solution should correctly handle all types of numbers and partition them based on their relation to the partition value.
Integer overflow if comparing very large numbers in the linked list	The solution should use appropriate comparison operators (e.g., using long type or other mitigation techniques depending on language/environment) to prevent integer overflow.

Empty list or null input list

How to Handle:

Return the original list or null, as there's nothing to partition.

List with only one element

How to Handle:

Return the original list, as it's already 'partitioned'.

Partition value is smaller than all elements in the list

How to Handle:

All elements should be moved to the 'greater than or equal' partition (right partition), leaving the 'less than' partition empty.

Partition value is larger than all elements in the list

How to Handle:

All elements should be moved to the 'less than' partition (left partition), leaving the 'greater than or equal' partition empty.

List contains duplicate values, some smaller and some greater than the partition value

How to Handle:

The duplicates should be grouped correctly on either side of the partition according to their value relative to the partition.

List is already partitioned correctly according to the value

How to Handle:

The solution should not modify the list in any way and should return it directly.

List contains negative numbers, zeros, and positive numbers

How to Handle:

The solution should correctly handle all types of numbers and partition them based on their relation to the partition value.

Integer overflow if comparing very large numbers in the linked list

How to Handle:

The solution should use appropriate comparison operators (e.g., using long type or other mitigation techniques depending on language/environment) to prevent integer overflow.

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 data type of the list elements and the partition value 'x'? Are they integers, floats, or something else?
Can the input list be empty or null? What should I return in those cases?
If a node's value is equal to 'x', where should it be placed in the partitioned list: before or after the group of nodes less than 'x'?
Does the relative order of nodes within each partition (less than x and greater than or equal to x) need to be preserved?
Is it guaranteed that 'x' will be present in the list? If not, how should I handle that scenario?

Brute Force Solution

Approach

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

Create one storage area to temporarily hold all values from the original list that are less than the given number.
Create another separate storage area to hold all the other values (those greater than or equal to the given number).
Go through the original list, one value at a time.
If a value is less than the given number, put it into the first storage area.
Otherwise, put the value into the second storage area.
Once we've moved all the values from the original list, take all the values from the first storage area and put them back into a new linked list.
Then, take all the values from the second storage area and add them to the end of that new linked list.
The resulting linked list is the rearranged list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def partition_list_brute_force(head, partition_value):
    less_than_partition = []
    greater_equal_partition = []

    current_node = head
    while current_node:
        # Append values to respective lists based on comparison.
        if current_node.val < partition_value:
            less_than_partition.append(current_node.val)

        else:
            greater_equal_partition.append(current_node.val)

        current_node = current_node.next

    new_head = None
    tail = None

    # Rebuild linked list using values from less_than_partition.
    for value in less_than_partition:
        new_node = ListNode(value)
        if not new_head:
            new_head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node

    # Append values from greater_equal_partition.
    for value in greater_equal_partition:
        new_node = ListNode(value)
        if not new_head:
            new_head = new_node
            tail = new_node
        else:
            # Only set if there are values in the first list.
            if tail:
                tail.next = new_node
            else:
                new_head = new_node
            tail = new_node

    return new_head

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have two empty boxes, one for numbers smaller than the target and another for numbers larger than the target.
Go through each number in the original list, one at a time.
If a number is smaller than the target, put it in the 'smaller' box.
If a number is larger than the target, put it in the 'larger' box.
Once you've processed all the numbers, take the 'smaller' box and connect it to the front of the 'larger' box. This combines the two lists in the desired order.

Code Implementation

def partition_list(head, partition_value):
    smaller_head = None
    smaller_tail = None
    larger_head = None
    larger_tail = None

    current_node = head

    while current_node:
        next_node = current_node.next

        if current_node.val < partition_value:
            # Build the list of nodes smaller than the partition value.
            if smaller_head is None:
                smaller_head = current_node
                smaller_tail = current_node
            else:
                smaller_tail.next = current_node
                smaller_tail = current_node
        else:
            # Build the list of nodes larger than or equal to the partition value.
            if larger_head is None:
                larger_head = current_node
                larger_tail = current_node
            else:
                larger_tail.next = current_node
                larger_tail = current_node

        current_node = next_node

    if larger_tail is not None:
        larger_tail.next = None

    # If there are no smaller nodes, return the larger list.
    if smaller_head is None:
        return larger_head

    # Connect the smaller list to the larger list.
    smaller_tail.next = larger_head

    # Return the head of the combined list.
    return smaller_head

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty list or null input list	Return the original list or null, as there's nothing to partition.
List with only one element	Return the original list, as it's already 'partitioned'.
Partition value is smaller than all elements in the list	All elements should be moved to the 'greater than or equal' partition (right partition), leaving the 'less than' partition empty.
Partition value is larger than all elements in the list	All elements should be moved to the 'less than' partition (left partition), leaving the 'greater than or equal' partition empty.
List contains duplicate values, some smaller and some greater than the partition value	The duplicates should be grouped correctly on either side of the partition according to their value relative to the partition.
List is already partitioned correctly according to the value	The solution should not modify the list in any way and should return it directly.
List contains negative numbers, zeros, and positive numbers	The solution should correctly handle all types of numbers and partition them based on their relation to the partition value.
Integer overflow if comparing very large numbers in the linked list	The solution should use appropriate comparison operators (e.g., using long type or other mitigation techniques depending on language/environment) to prevent integer overflow.

Empty list or null input list

How to Handle:

Return the original list or null, as there's nothing to partition.

List with only one element

How to Handle:

Return the original list, as it's already 'partitioned'.

Partition value is smaller than all elements in the list

How to Handle:

All elements should be moved to the 'greater than or equal' partition (right partition), leaving the 'less than' partition empty.

Partition value is larger than all elements in the list

How to Handle:

All elements should be moved to the 'less than' partition (left partition), leaving the 'greater than or equal' partition empty.

List contains duplicate values, some smaller and some greater than the partition value

How to Handle:

The duplicates should be grouped correctly on either side of the partition according to their value relative to the partition.

List is already partitioned correctly according to the value

How to Handle:

The solution should not modify the list in any way and should return it directly.

List contains negative numbers, zeros, and positive numbers

How to Handle:

The solution should correctly handle all types of numbers and partition them based on their relation to the partition value.

Integer overflow if comparing very large numbers in the linked list

How to Handle:

The solution should use appropriate comparison operators (e.g., using long type or other mitigation techniques depending on language/environment) to prevent integer overflow.