Sorting a Linked List of 0's, 1's and 2's

Problem Statement:-

Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to the head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.


Example 1:

Input:
N = 8
value[] = {1,2,2,1,2,0,2,2}
Output: 0 1 1 2 2 2 2 2
Explanation: All the 0s are segregated
to the left end of the linked list,
2s to the right end of the list, and
1s in between.

Solution:-

The basic approach to solve this problem would be to store the count of  0's, 1's, and 2's and then changing the value of the nodes of the LinkedList. 

And this is an optimal approach as well, many people will argue that since we are storing the count of  0's, 1's, and 2's, it will be using O(N) extra space. But no, we will be using O(1) space to store the count of elements, since, for each test case, we will only require to store the count of 3 numbers (0, 1, 2). 

Let us now look at the solution:

Node* segregate(Node *head) {
    // first we will be checking if the linked list passed is
    // valid or not
    if(!head){
        return head;
    }
    Node *ptr = head;
    
    // to store the count of 0, 1 and 2
    int count[3] = {0, 0, 0};
    while(ptr){
        ++count[ptr->data];
        ptr=ptr->next;
    }
    ptr = head;
    int i = 0;
    
    // updating the value of each node
    while(ptr){
        if(count[i]==0){
            ++i;
        }else{
            ptr->data = i;
            ptr = ptr->next;
            --count[i];
        }
    }
    return head;
}
Let us now analyze our solution:

The space complexity for this solution would be O(1) since we are not using any extra space for this. The space used will be constant.

The time complexity for this solution would be O(N), where N is the number of nodes in the linked list. We will be traversing the entire linked list to store the count of 0's, 1's, and 2's and then we will again traverse the entire linked list to update the value of each node in ascending order. 

You may also refer to my Github Repo where I keep uploading solutions for multiple DSA problems daily.


Comments

Post a Comment

Popular posts from this blog

Finding the minimum and maximum element in an array

Image
Welcome file Problem Statement :- Finding the minimum and maximum element in a given array Example 1: We will be given an array and we need to output two space separated integers. First integer should be the minimum number in the array and the second interger should be the maximum number in the array. Input: {15, 1, -9, 76, 28, 1} Output: -9 76 Explanation: -9 is the smallest integer and 76 is the largest integer in the given array. Solution:- The above problem can be solved in multiple ways, but I will be discussing two basic approaches to solve the problem. Using Sorting:- In this method, we need to sort the array first. Let’s say we have sorted the array in ascending order. This means that the first element of the array will now be the minimum element and the last element in the array would be maximum element. The solution is easy to implement and really easy to understand as well, but the only issue that we might face during the interview will be it...
Read more

Reversing an Array

Temp Reverse the Array Example 1: The problem is quite straight forward, we have to reverse the array given to us. Input: N = 8 value[] = {1,2,3,4,5,2,1,7,8} Output[] = {8,7,1,2,5,4,3,2,1} Explanation: The elements of the array are reversed. Solution:- There could be multiple ways to solve this problem, but I will be discussing two approaches. First of all I will be discussing the very basic approach (Brute Force) and then I will be discussing the most optimal approach in terms of space and time to solve the same problem. Brute Force Solution:- In this approach, we will be using an extra array. We will be traversing the given array from end to start and keep storing the values in the new array. Now, the new array will be having the elements in reverse order of the original array. This solution will be using O(N) extra space to store the elements in the new array, and we will have to traverse the entire array resulting in O(N) time complexity. Here is ...
Read more