Amazon Prime




 
Tagged
  • Algorithm
  • Two Pointer Technique
  •  

    Two Pointer Technique

    Introduction

    Two Pointers technique is mainly used to search for data in a given data structure. This optimization technique helps to solve the problem efficiently and effectively in terms of both time and space complexities.

    In this technique two pointers scan over data structure simultaneously to find the desired elements in the data structure. This technique is mainly used on data structures like arrays, linked lists, queues, strings etc.

    Middle of the Linked List

    To learn about linked list data structure, visit Linked List Tutorial.

    Let us understand the concept of two pointer technique using simple problem "Find middle of the linked list"

    1Problem Description :
    2Given a singly linked list A, find the middle element of the linked list.
    3
    4NOTE :
    51) You are given only head node of the linked list
    62) Length of the linked list is not known
    73) If there are even nodes in the linked list, there would be two middle nodes,in this case return the second middle element.
    8
    9
    10Input:
    11A pointer to the head of the linked list.
    12
    13Output:
    14Return middle of the linked list.
     
    1Example 1 :
    2
    3 Input : 5 -> 7 -> 3 -> 10 -> 17
    4
    5 Output: 3
    6
    7 Explanation : The middle element of the linked list is 3
     
    1Example 2 :
    2
    3 Input : 15 -> 4 -> 7 -> 3
    4
    5 Output: 7
    6
    7 Explanation : As the linked list has even number of nodes, both 4 and 7 are middle elements of the linked list, In this case we return second middle element which is 7.

    Solution Approaches

    • By finding the length of the Linked List
    • Using Two Pointer Technique

    Using Number of Nodes

    Algorithm

    1Step 1: Find length (len) of the linked list by traversing nodes from head
    2Step 2: Now iterate the linked list len/2 times
    3Step 3: return len/2 node as output

    Implementation

    1public class MiddleOfTheLinkedList {
    2
    3 public ListNode getMiddleNode(ListNode head) {
    4 // initialize current pointer to head of the linked list
    5 ListNode current = head;
    6
    7 // initialize a variable to get length of the linked list
    8 int n = 0;
    9
    10 // iterate through linked list to increment length
    11 while(current!= null){
    12 n++;
    13 current = current.next;
    14 }
    15 System.out.println("size is "+n);
    16
    17 // set current pointer to head of the linked list
    18 current = head;
    19
    20 // Now move current pointer n/2 times to get the middle node.
    21 for(int i=0;i<n/2;i++){
    22 current = current.next;
    23 }
    24 // return middle node of the linked list
    25 return current;
    26 }
    27
    28 // helper method to create a linked list easily
    29 // by giving values in the form of array
    30 // input : array
    31 // output : linked list (head node of the linked list)
    32 public ListNode create(int [] array) {
    33
    34 // create dummy node as first node for simplicity of the code
    35 ListNode head = new ListNode(0);
    36 ListNode current = head;
    37
    38 for(int i=0; i<array.length; i++){
    39 current.next = new ListNode(array[i]);
    40 current = current.next;
    41 }
    42 // as first node is dummy node
    43 // return head.next which is actual header
    44 return head.next;
    45 }
    46
    47 class ListNode {
    48 ListNode next;
    49 int val;
    50
    51 ListNode(int data) {
    52 this.val = data ;
    53 }
    54 }
    55
    56 // Driver method
    57 public static void main(String[] args){
    58 MiddleOfTheLinkedList obj = new MiddleOfTheLinkedList();
    59
    60 int[] input1 = {7, 3, 5, 17, 21, 25, 81};
    61 ListNode head = obj.create(input1);
    62 ListNode middle = obj.getMiddleNode(head);
    63 if(middle != null) {
    64 System.out.println(middle.val);
    65 }
    66
    67 int[] input2 = {7, 3, 5, 17, 21, 25, 81, 90};
    68 head = obj.create(input2);
    69 middle = obj.getMiddleNode(head);
    70 if(middle != null) {
    71 System.out.println(middle.val);
    72 }
    73 }
    74
    75}

    Complexity Analysis

    • Time Complexity : O(n) where n is the length of the linked list
    • Space Complexity: O(1)

    Two Pointer Technique

    Algorithm

    1Step 1 : Initialize two pointers slow and fast at head of the linked list
    2Step 2 : Traverse over the linked list by stepping fast pointer by 2 steps and slow pointer by 1 step a head until fast pointer reached the end of the linked list
    3Step 3 : return slow pointer (Here slow pointer is at n/2 position of the linked list as every time fast pointer stepping ahead 2 times)

    MiddleOfLinkedList - TwoPointerTechnique

    Implementation

    1public class MiddleOfTheLinkedListUsingTwoPointerTechnique {
    2
    3 public ListNode getMiddleNode(ListNode head) {
    4 // initialize slow and fast pointer to head of the linked list
    5 ListNode slow = head;
    6 ListNode fast = head;
    7
    8 // iterate through linked list
    9 // move slow pointer one step ahead
    10 // and fast pointer to two steps ahead
    11 // repeat the same until fast pointer reaches end of the linked list
    12 while(fast != null && fast.next != null){
    13 System.out.println(fast.val +" "+ slow.val);
    14 slow = slow.next;
    15 fast = fast.next.next;
    16 }
    17 // return middle node of the linked list
    18 return slow;
    19 }
    20
    21 // helper method to create a linked list
    22 // easily by giving values in the form of array
    23 // input : array
    24 // output : linked list (head node of the linked list)
    25 public ListNode create(int [] array) {
    26
    27 // create dummy node as first node for simplicity of the code
    28 ListNode head = new ListNode(0);
    29 ListNode current = head;
    30
    31 for(int i=0; i<array.length; i++){
    32 current.next = new ListNode(array[i]);
    33 current = current.next;
    34 }
    35 // as first node is dummy node
    36 // return head.next which is actual header
    37 return head.next;
    38 }
    39
    40 // ListNode class
    41 class ListNode {
    42 ListNode next;
    43 int val;
    44
    45 ListNode(int data) {
    46 this.val = data ;
    47 }
    48 }
    49
    50 // Driver method
    51 public static void main(String[] args){
    52 MiddleOfTheLinkedListUsingTwoPointerTechnique obj =
    53 new MiddleOfTheLinkedListUsingTwoPointerTechnique();
    54
    55 int[] input1 = {7, 3, 5, 17, 21, 25, 81};
    56 ListNode head = obj.create(input1);
    57 ListNode middle = obj.getMiddleNode(head);
    58 if(middle != null) {
    59 System.out.println(middle.val);
    60 }
    61
    62 int[] input2 = {7, 3, 5, 17, 21, 25, 81, 90};
    63 head = obj.create(input2);
    64 middle = obj.getMiddleNode(head);
    65 if(middle != null) {
    66 System.out.println(middle.val);
    67 }
    68 }
    69}

    Complexity Analysis

    • Time Complexity : O(n) where n is the length of the linked list
    • Space Complexity: O(1)

    Significance

    Even though both approaches take O(n) time complexity, in approach 1 we are traversing the linked list two times, whereas in two pointer technique we do traverse the linked list one time to find the middle of the linked list. This way the two-pointer technique helps to optimize the solution effectively.

     

  • Algorithm
  • Two Pointer Technique
  •  
    ...