Arrange the Salary

CONCEPTS USED:

Basic Pointer Manipulation

DIFFICULTY LEVEL:

Medium

PROBLEM STATEMENT(SIMPLIFIED):

Given a linked list of N elements and a value X, your task is to arrange the list in such a way that all elements less than X comes first, then finally all elements greater than or equal to X.

NOTE : You have to maintain the original relative order of the elements at the time of arranging the salary.

See original problem statement here

For Example:

Input :  

list = 9 -> 6 -> 3 -> 7 -> 1 -> 4
K = 5

Output: 3 -> 1 -> 4 -> 9 -> 6 -> 7

Explaination : Elements smaller than 5 i.e. 3, 1, 4 are arranged at the starting while elements greater than 5 are arranged after them without changing the relative order of all the elements.

SOLVING APPROACH:

BRUTE FORCE METHOD:

  1. The idea is to go through a best website to learn java and to create two additional arrays min_arr and max_arr for storing the elements less than X in min_arr while to store elements greater than or equal to X in max_arr.

  2. Then simply print elements from min_arr first and then max_arr.

  3. This approach is not efficient as it uses additional O(N) space.

SOLUTIONS:


#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
    int data;
    struct Node *next;
}Node;
Node* temp = NULL;
Node* insert(Node *head, int data) {
    if(head == NULL) {
        head = new Node();
        head->data = data;
        head->next = NULL;
        return temp = head;
    }
    Node* node = new Node();
    node->data = data;
    node->next = NULL;
    temp->next = node;
    temp = temp->next;
    return head;
}

void print(Node *head) {
    if(head->next == NULL) {
        cout << head->data << " ";
        return;
    }
    cout << head->data << " ";
    print(head->next);
}

Node* ArrangeSalary(Node* head, int X) {

    if(head == NULL || head->next == NULL)
      return head;

    Node *temp = head;

    vector<int> v_min, v_max;
    while(temp != NULL){
      if(temp->data < X)
        v_min.push_back(temp->data);
      else
        v_max.push_back(temp->data);
      temp = temp->next;
    }

    temp = head;

    while(temp != NULL){
      if(!v_min.empty()){
        temp->data = v_min.front();
        v_min.erase(v_min.begin());
      }
      else if(!v_max.empty()){
        temp->data = v_max.front();
        v_max.erase(v_max.begin());
      }

      temp = temp->next;
    }
    return head;

}

int main()
{

    Node *head = NULL;
    Node *ptr = NULL;
    int n, X;
    cin >> n >>X;
    for(int i=0; i<n; i++) {
        int data;
        cin >> data;
        head = insert(head, data);
    }
    head = ArrangeSalary(head, X);
    print(head);
    cout << endl;
    return 0;
}

EFFICIENT METHOD:

  1. The idea is to create two linked list and initialize their head nodes as NULL -
    • smaller list of values smaller than X.
    • larger list of values greater than or equal to X.
  2. Now traverse the original list and if an element is less than X, append it to the end of the smaller list else append it to the end of the larger list. Finally concatenate both the smaller and larger lists to form the resultant list.

SOLUTIONS:


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node *next;
}Node;
Node* getNode (Node*head, int val)
{
    Node *element = (Node*) malloc(sizeof(Node));
    element->data = val ;
    element->next = NULL ;
    Node *temp = head ;
    if ( head == NULL ) {
        head = element ;
        head->next = NULL ;
        return head ;
    }
    while (temp->next != NULL)
        temp = temp->next ;
    temp->next = element ;
    element->next = NULL ;
    return head ;
}


void print(Node *head) {
    if(head->next == NULL) {
        printf("%d ", head->data);
        return;
    }
    printf("%d ", head->data);
    print(head->next);
}

Node* ArrangeSalary(Node* head, int X) {

  /* if list has 0 or 1 elements then return */
  if(head == NULL || head->next == NULL)
    return head;

  /* create two lists one for storing smaller elements than X and
    another for storing greater than or equal to elements than X */

  /* head pointer for smaller list */
  Node *smaller = NULL ;

  /*pointer to the last element in the smaller list */
  Node *temp_smaller;

   /* head pointer for greater list */
  Node *greater = NULL ;

  /*pointer to the last element in the greater list */
  Node *temp_greater ;

  Node *temp = head;

  while(temp != NULL){
    Node* t = temp;
    temp = temp -> next;

    if(t->data < X){
      if(smaller == NULL){
        smaller = t;
        temp_smaller = t;
        t -> next = NULL;
      }
      else{
        temp_smaller -> next = t;
        t -> next = NULL;
        temp_smaller = t;
      }

    }
    else{
      if(greater == NULL){
        greater = t;
        temp_greater = t;
        t -> next = NULL;
      }
      else{
        temp_greater -> next = t;
        t -> next = NULL;
        temp_greater = t;
      }
    }
  }

  /* concatenating both smaller and greater lists */
  temp_smaller -> next = greater;

  return smaller;

}
int main()
{

    Node *head = NULL;
    int n, X;
    scanf("%d %d", &n,&X);
    for(int i=0; i<n; i++) {
        int data;
        scanf("%d", &data);
        head = getNode(head, data);
    }
    head = ArrangeSalary(head, X);
    print(head);
    printf("\n");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef struct Node {
    int data;
    struct Node *next;
}Node;
Node* temp = NULL;
Node* insert(Node *head, int data) {
    if(head == NULL) {
        head = new Node();
        head->data = data;
        head->next = NULL;
        return temp = head;
    }
    Node* node = new Node();
    node->data = data;
    node->next = NULL;
    temp->next = node;
    temp = temp->next;
    return head;
}

void print(Node *head) {
    if(head->next == NULL) {
        cout << head->data << " ";
        return;
    }
    cout << head->data << " ";
    print(head->next);
}

Node* ArrangeSalary(Node* head, int X) {

  /* if list has 0 or 1 elements then return */
  if(head == NULL || head->next == NULL)
    return head;

  /* create two lists one for storing smaller elements than X and
    another for storing greater than or equal to elements than X */

  /* head pointer for smaller list */
  Node *smaller = NULL ;

  /*pointer to the last element in the smaller list */
  Node *temp_smaller= NULL;

   /* head pointer for greater list */
  Node *greater = NULL ;

  /*pointer to the last element in the greater list */
  Node *temp_greater = NULL;

  Node *temp = head;

  while(temp != NULL){
    Node* t = temp;
    temp = temp -> next;

    if(t->data < X){
      if(smaller == NULL){
        smaller = t;
        temp_smaller = t;
        t -> next = NULL;
      }
      else{
        temp_smaller -> next = t;
        t -> next = NULL;
        temp_smaller = t;
      }

    }
    else{
      if(greater == NULL){
        greater = t;
        temp_greater = t;
        t -> next = NULL;
      }
      else{
        temp_greater -> next = t;
        t -> next = NULL;
        temp_greater = t;
      }
    }
  }

  /* concatenating both smaller and greater lists */
  temp_smaller -> next = greater;

  return smaller;
}

int main()
{

    Node *head = NULL;
    Node *ptr = NULL;
    int n, X;
    cin >> n >>X;
    for(int i=0; i<n; i++) {
        int data;
        cin >> data;
        head = insert(head, data);
    }
    head = ArrangeSalary(head, X);
    print(head);
    cout << endl;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static class SinglyLinkedListNode {
        public int value;
        public SinglyLinkedListNode next;

        public SinglyLinkedListNode(int nodeData) {
            this.value = nodeData;
            this.next = null;
        }
    }

    static class SinglyLinkedList {
        public SinglyLinkedListNode head;
        public SinglyLinkedListNode tail;

        public SinglyLinkedList() {
            this.head = null;
            this.tail = null;
        }

        public void insertNode(int nodeData) {
            SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
            }

            this.tail = node;
        }
    }

    static void printLinkedList(SinglyLinkedListNode head) {
        SinglyLinkedListNode temp = head;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
        System.out.println();
    }

static SinglyLinkedListNode ArrangeSalary(SinglyLinkedListNode head, int X) {

    /* if list has 0 or 1 elements then return */
    if(head == null || head.next == null)
      return head;

    /* create two lists one for storing smaller elements than X and
      another for storing greater than or equal to elements than X */

    /* head pointer for smaller list */
    SinglyLinkedListNode smaller = null;

    /*pointer to the last element in the smaller list */
    SinglyLinkedListNode temp_smaller = null;

     /* head pointer for greater list */
    SinglyLinkedListNode greater = null;

    /*pointer to the last element in the greater list */
    SinglyLinkedListNode temp_greater = null;

    SinglyLinkedListNode temp = head;

    while(temp != null){
      SinglyLinkedListNode t = temp;
      temp = temp.next;

      if(t.value < X){
        if(smaller == null){
          smaller = t;
          temp_smaller = t;
          t.next = null;
        }
        else{
          temp_smaller.next = t;
          t.next = null;
          temp_smaller = t;
        }

      }
      else{
        if(greater == null){
          greater = t;
          temp_greater = t;
          t.next = null;
        }
        else{
          temp_greater.next = t;
          t.next = null;
          temp_greater = t;
        }
      }
    }

    /* concatenating both smaller and greater lists */
    temp_smaller.next = greater;

      return smaller;
}


    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {

        SinglyLinkedList llist = new SinglyLinkedList();
        int size = scanner.nextInt();
        int X = scanner.nextInt();

        for (int i = 0; i < size; i++) {
            int llistItem = scanner.nextInt();

            llist.insertNode(llistItem);
        }
        SinglyLinkedListNode temp = ArrangeSalary(llist.head, X);
        printLinkedList(temp);

    }
}

Space Complexity: O(1)

Previous post Contest Winner
Next post Arrange the List

Leave a Reply

Your email address will not be published. Required fields are marked *