This is a very common question asked in many programming competitions and interviews. In this article we will understand how to solve this problem.
There are two main approaches to this problem. One which strikes immediately and another which comes up by observing something. These two approaches are:
- Brute force
- Two pointers
Let’s have a look at both of these approaches.
Brute force solution
This solution comes to our mind with our experience with arrays. Suppose this question was asked in context of arrays then our answer would be straight forward, i.e.,
Last Kth element in the array (P) = Length of the array – K
Index of the last Kth element in the array (since arrays indexes are 0 based) (Q) = P – 1
So, the answer would be array[Q]
Same approach we are going to take in the case of linked list also. We will first count the total number of elements in the linked list and then traverse it again till the Kth element and return it.
private static int getLastKthElementBruteForce(Node head, int k) {
int count = 0;
Node current = head;
while (current != null) {
count++;
current = current.next;
}
int lastKthIndex = (count - k) - 1;
int index = 0;
current = head;
while (index < lastKthIndex) {
current = current.next;
index++;
}
return current.data;
}Two pointers solution
Before we dive into discussing this approach, let’s first understand what was the drawback of the previous solution.
Let’s talk about the time complexity of the brute force approach. First, we are iterating on the whole list to find out the number of elements present that gives us O(n). Then we are again traversing it find the relevant element which gives us O(n). So, the whole solution gives us 2O(n) ≈ O(n).
O(n) seems fine for a linked list but let’s count the number of operations. In the first pass we will have N operations where N is the number of elements present in the list. And in the second pass we will have (N – K) operations where K being the position of the element from the end. So, total operations will be N + (N – K).
Now, assume N to be 1000 and K to be 34 i.e., we want to find the 34th element from the end of the list. Total operations in this case would be – 1000 + (1000 – 34) = 1966. Let’s understand the two pointers approach and do the same calculation for it.
Two pointers solution works on the observation that if we have a direct reference to the Kth element from the end then obviously the gap or the distance between this node and the end node will be K. Now, we can achieve this by having two traversal pointers with a distance of K moving simultaneously. Since the distance between them is K, when the front pointer reaches the end, the back pointer will be pointing to the last Kth element of the list.
Below is the implementation for this approach.
private static int getLastKthElementTwoPointer(Node head, int k) {
Node front = head;
Node back = head;
int index = 1;
while (index <= k) {
front = front.next;
index++;
}
while (front.next != null) {
front = front.next;
back = back.next;
}
return back.data;
}Let’s talk about the time complexity of this solution. In the first loop we are traversing first K elements so, the complexity would be O(K). In the second loop we are traversing the remaining N – K elements with an extra constant operation of moving the back pointer as well. So, the complexity would be O(N – K). With this the total complexity comes out to be O(K + N – K) = O(N).
Now, it seems that what difference does this approach make as both have the same time complexity. And for that reason, we calculated the exact number of iterations for the brute force approach. Let’s do the same for this one.
Taking the same example where N = 1000 and K = 34. In the first pass total iterations would be 34 and in the second pass the number of iterations would be 1000 – 34 = 966. So, the total number of iterations would be 34 + 966 = 1000 which is same as the number of elements in the list. And here lies the difference that to find out the last Kth element, in the given example, we did 966 extra iterations which is not the case in two pointers approach. Hence, the two pointers approach is preferred to solve this problem.
Complete program
package com.theaconitedev;
public class Main {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
Node head = getList();
int k = 4;
System.out.println("Brute force = " + getLastKthElementBruteForce(head, k));
System.out.println("Two pointers = " + getLastKthElementTwoPointer(head, k));
}
private static Node getList() {
Node head = null;
Node current = null;
for (int i = 1; i <= 10; i++) {
Node node = new Node(i);
if (i == 1) {
head = node;
} else {
current.next = node;
}
current = node;
}
return head;
}
private static int getLastKthElementBruteForce(Node head, int k) {
int count = 0;
Node current = head;
while (current != null) {
count++;
current = current.next;
}
int lastKthIndex = (count - k) - 1;
int index = 0;
current = head;
while (index < lastKthIndex) {
current = current.next;
index++;
}
return current.data;
}
private static int getLastKthElementTwoPointer(Node head, int k) {
Node front = head;
Node back = head;
int index = 1;
while (index <= k) {
front = front.next;
index++;
}
while (front.next != null) {
front = front.next;
back = back.next;
}
return back.data;
}
}
Brute force = 6 Two pointers = 6