Last occurrence of element with binary search

Last occurrence of element

This problem is very similar to First occurrence of element with binary search. Given a sorted array and an element, find last occurrence of element in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find last index. For example, in given array, last occurrence of 4 is at index 4. Can you guess what is last occurrence of element 6?

last occurrence of element

Brute force solution would be to scan entire array and compare each A[index] with key. If A[index] is equal to key and next element is not equal key, then return index. Worst case time complexity of brute force method is O(N). Can we do better than it?

Last occurrence of element : Thought process

One property of input array we did not use in brute force solution is array being sorted. To search in sorted array: binary search algorithm . If there are no duplicates in array, it will be super easy to find last occurrence using binary search, how can we modify it to solve problem with duplicates.
First question you should ask to yourself : What is candidate solution set? In plain terms, what can be a valid answer if there is key is present? Also, think about case when key is not present at all.

If key is present, candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned one concept  when solving for find greater or equal number or ceiling in sorted array. The concept was, we can apply binary search to any set of input where following condition is met :

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x or for all y < x

If A[index] is less than or equal to key, than all A[y] will be less than or equal to A[index] where y < index, which satisfies our condition to apply binary search.
This means when predicate return true, which is : element equal or less than key, there is no point looking into left subarray, as all elements will be less than or equal to key. Last occurrence of key can not be less than current index. Hence, discard Array[start, index-1] and look in right side of array, Array[index, end].
What should be start point for index? Obviously, it will be mid index. Based on if predicate(mid) is true or false, we discard left or right half of array.

When to stop? When just one element in array. at that point, check if that element is key, if yes return index else return -1.

Last occurrence of element in sorted array : Example

Let’s take an example and see how it works? Take an array as shown below and find last occurrence of element 2.

 

Start with mid index and see if it is less than or equal to key, it is, so discard left subarray excluding mid.

 

New array to be searched is from index 3 to 7. Find new mid, element at new mid is less than or equal to key, in that case discard left subarray.

Search space is reduced from index 5 to 7. Mid is 6 and Array[6] is greater than key, so again discard right subarray.

 

 

At this point, there is only one element left in candidate set. Is it equal to key? If yes, return the index.

last occurrence of element

 

Can you please draw the execution flow to find 1 and say 10 (which does not exist in array)? Does algorithm work for those cases?

Last occurrence of element in sorted array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    private static boolean isLessThanEqualTo(int[] a, int index, int key){
        if(a[index] <= key) return true;

        return false;
    }

    public static int findLastOccurrence (int[] a, int start, int end, int key){

        while(start < end){
            int mid = start + ((end - start) +1) / 2;

            if(isLessThanEqualTo(a, mid, key)){
                start = mid;
            }
            else{
                end= mid-1;
            }
        }
        return (a[start] == key) ? start : -1;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,17,17,20};

        int index = findLastInstance(input,0, input.length-1, 20);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);
    }
}

Same method can be implemented recursively as follow

public static int findLastOccurrence Recursive(int[] a, int start, int end, int key){

    while(start < end){
        int mid = start + ((end - start) +1) / 2;

        if(isLessThanEqualTo(a, mid, key)){
            return findLastOccurrenceRecursive(a,mid,end, key);
        }
        else{
            return findLastOccurrenceRecursive(a,start,mid-1, key);
        }
    }
    return (a[start] == key) ? start : -1;
}

Worst case complexity to find last occurrence of element in sorted array using binary search algorithm is O(log n).

What did we learn from this problem? First, how to identify if a problem can be solved using binary search. We learned how solution depends on candidate solution set. How can we discard some part of that set based on constraints in problem. For example, in this problem, candidate set was all indices of array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check last element for constraints of problem, if matches, then it is solution, else there is no solution.

Hope, this article helps you to prepare better for your interviews. If you find anything missing or wrong, please reach out to us through comments, email at communications@algorithmsandme.com

First occurrence of element with binary search

First occurrence of element in sorted array

Given a sorted array and an element, find the first occurrence of key in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find first index. For example, in given array, first occurrence of 4 is at index 3. Can you guess what is first occurrence of element 6?

first occurrence of element

Brute force solution would be to scan entire array and compare each A[index] with key. If A[index]  == key, then return index. Worst case time complexity of brute force method is O(N). Can we do better than it?

First occurrence of element : Thought process

One property of input array we did not use in brute force solution is array being sorted. To search in sorted array: binary search algorithm . If there are no duplicates in array, it will be super easy to find first instance using binary search, how can we modify it to solve problem with duplicates.
First question you should ask to yourself : What is candidate solution set? In plain terms, what can be a valid answer if there is key is present? Also, think about case when key is not present at all.

If key is present, candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned one concept  when solving for find greater or equal number or ceiling in sorted array. The concept was, we can apply binary search to any set of input where following condition is met :

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x.

If A[index] is greater than or equal to key, than all A[y] will be greater than or equal to A[index] where y > index, which satisfies our condition.
This means when predicate return true, there is no point looking into right subarray, as all elements will be greater than or equal to key. First instance of key can not be more than index. Hence, discard Array[index+1, end] and look in left side of array, Array[start, index].
What should be start point for index? Obviously, it will be mid index. Based on if predicate(mid) is true or false, we discard right or left half of array.

When to stop? When just one element in array. at that point, check if that element is key, if yes return index else return -1.

First occurrence of element in sorted array : Example

Let’s take an example and see how it works? Take an array as shown below and find first instance of element 6.

Start with mid index and see if it is greater than or equal to key, it is not, so discard the left subarray including mid.

New array to be searched is from index 5 to 9. Find new mid, element at new mid is greater than or equal to key, in that case discard right subarray.

Search space is reduced from index 5 to 7. Mid is 6 and Array[6] is equal to key, so again discard right subarray.

first occurrence of element

Find mid again, which is 5. Array[5] is equal to key, so discard right sub array.

first occurrence of element

At this point, there is only one element left in candidate set. Is it equal to key? If yes, return the index.

first instance of element in sorted array Can you please draw the execution flow to find 1 and say 10 (which does not exist in array)? Does algorithm work for those cases?

First occurrence of element in sorted array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    private static boolean isGreaterThanEqualTo(int[] a, int index, int key){
        if(a[index] >= key) return true;

        return false;
    }

    public static int findFirstOccurrence (int[] a, int start, int end, int key){

        while(start < end){
            int mid = start + (end - start) / 2;

            if(isGreaterThanEqualTo(a, mid, key)){
                end = mid;
            }
            else{
                start = mid + 1;
            }
        }
        return (a[start] == key) ? start : -1;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,17,17,20};

        int index = findFirstInstance(input,0, input.length-1, 20);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);
    }
}

Same method can be implemented recursively as follow

public static int findFirstOccurrence Recursive(int[] a, int start, int end, int key){

    while(start < end){
        int mid = start + (end - start) / 2;

        if(isGreaterThanEqualTo(a, mid, key)){
            return findFirstOccurrenceRecursive(a,start,mid, key);
        }
        else{
            return findFirstOccurrenceRecursive(a,mid+1,end, key);
        }
    }
    return (a[start] == key) ? start : -1;
}

Worst case complexity to find first occurrence of element in sorted array using binary search algorithm is O(log n).

What did we learn from this problem? First, how to identify if a problem can be solved using binary search. We learned how solution depends on candidate solution set. How can we discard some part of that set based on constraints in problem. For example, in this problem, candidate set was all indices of array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check last element for constraints of problem, if matches, then it is solution, else there is no solution.

Hope, this article helps you to prepare better for your interviews. If you find anything missing or wrong, please reach out to us through comments, email at communications@algorithmsandme.com

Minimum in sorted rotated array

Find Minimum  in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.  Problem today is bit different, there is no key to find first of all. Ask of problem is to find minimum in sorted rotated array.

To understand problem, first let’s understand what is sorted array and then what is sorted rotated array.

An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements of array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again, all elements are moved to right, it’s rotation by 2 and so on.

Find element in sorted rotated array
Sorted array
Sorted rotated array

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

Find minimum in sorted rotated array : Thought process

As always, first come up with a brute force solution without worrying about any optimizations as of now. Simplest way would be to scan through array and keep track of minimum. Complexity of this method is O(N), however, what is the fun if we do it in O(N) time complexity ?

In brute force solution, we did not use the fact that array is sorted and then rotated. Let’s forget about rotation and concentrate only in sorted part.

What is minimum element in sorted array? Obviously, it is the first element of array. We see that all the elements on right side of minimum elements are greater than minimum.

What will happen if start rotating array now, is the condition that all the elements on right of minimum element are greater than it still hold? Yes, it does. Either there will be no element on right side of minimum or the will be definitely greater than it.

So, idea is we randomly pick an element and see if elements on right side of it are greater. No need to go through each element, compare selected element with last index element, if last index element is greater, selected element can be minimum. (Remember we are working sorted array!).
Start comparing with middle element. What information comparison between middle and end element gives us?
Array could have been in two ways : It is rotated more than half or it is rotated less than half.
If middle element is less than last element, array is rotated less than half, and hence, minimum element should be on the left half of array.
If middle element will be greater than last element, array is rotated more than half, hence minimum element should be in right part of array.
What if middle element is the minimum element? See if element on left and right of mid are both greater than element at mid, mid is index of minimum element.
Let’s take an example and see how this method works and then come up with concrete algorithm to find minimum in sorted rotated array. For example, array is given as below.
minimum in sorted rotated array
First, we find the mid, check if mid is minimum?  A[mid] > A[mid-1], so it cannot be minimum element. So, see if array is rotated more than half or less than half.
Since, A[mid] > A[end], array is rotated more than half and hence, minimum should be on the right side.
We will discard the left subarray and focus on right subarray to find minimum.
Again, find the mid, is mid the minimum? No, so compare it with end, since, A[mid] < A[end],  minimum should be on the left side, discard right subarray.
Find mid again and this time mid satisfy the condition : A[mid-1] and A[mid+1] both are greater than A[mid], hence, A[mid] should be the minimum element.
minimum in sorted rotated array
Can you come up with execution trace when array is not rotated more than half to start with?

Minimum in sorted rotated array : Algorithm

  1. Find mid = start + (end- start) /2
  2. See if mid is minimum element i.e is A[mid] < A[mid-1] and A[mid] < A[mid+1]. If yes, return mid
  3. Else if A[mid] > A[end]:
    • Array is rotated more than half, minimum should be on right subarray
    • Continue with subarray with start =  mid+1
  4. Else if A[mid] < A[end]:
    • Array is rotated less than half, minimum should be on left subarray
    • Continue with subarray with end = mid-1

Minimum in sorted rotated array implementation

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

    public static int findMinimumIterative(int[] input, int start, int end) {

        while (start < end) {
            int mid = start + (end - start) / 2;

            if (mid == 0 || (input[mid] <= input[mid+1]
                    && input[mid] < input[mid-1])) return mid;
            else if (input[mid] > input[mid]) {
                 /* Array is rotated more than half, hence minimum
                 should be in right sub-array
                  */
                start  = mid + 1;
            } else {
                 /* Array is rotated less than half, hence minimum
                 should be in left sub-array
                  */
                end  = mid - 1;
            }
        }
        return start;
    }
    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,3,3,3,3,3};

        int index = findMinimumIterative(input,0, input.length-1);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Recursive implementation of same function

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

    public static int findMinimumRecursive(int[] input, int start, int end){

        if(start < end){
            int mid = start + (end - start) / 2;

            if(mid == 0 || (input[mid] < input[mid-1]
                            && input[mid] <= input[mid+1] ) ) return mid;

            else if(input[mid] > input[end]){
                /* Array is rotated more than half and hence,
                search in right subarray */
                return findMinimumRecursive(input, mid+1, end);
            }else {
                return findMinimumRecursive(input, start, mid - 1);
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,18,19,20};

        int index = findMinimumRecursive(input,0, input.length-1);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Complexity of algorithm to find minimum in sorted rotated array is O(log N), with recursive implementation having implicit space complexity of O(log N).

What did we learn from this problem?
First learning is to always go for brute force method. Second, try to draw the effect of any additional operations which are done on original array. In sorted rotated array, try to have rotation one by one and see what impact it has on minimum element? Try to classify individual class and design your algorithm. In this problem, we identify that based on how many times array is rotated, minimum can be in right or left subarray from middle and that gave idea for discarding half of the array.

Please share if there is something wrong or missing, or any improvement we can do. Please reach out to us if you are willing to share your knowledge and contribute to learning process of others.

Most frequent words in file

Most frequent words in file

In last post:  find K smallest element in an array, we learned some concepts to find top or bottom element in a given set. Let’s apply those concept again to a different problem called most frequent words in a file.

Given a text file which contains strings/words, find n most frequently occurring words in it i.e. n words whose count is the maximum.

For example, if given file is like follows: one, two, two, three, three, three, four,four, four,four, five, five, five, five, five, six,six, six, six, six, six  and we are looking for three most frequent words, output should be :  six,five, four.

Line of thoughts

Brute force solution would be really easy, scan the whole file, get the count for each unique words in file. Then sort the output based on that count in descending order and then return first n words.

This problem has three parts to it. First, read all words from file, second created a map which store frequency count of each word on file. Third is to get top n words from that map.

Reading a file is pretty standard operation in any language.  Brush upon Java basics here. We will not focus on that and also that’s not the intention of this question.
Assuming we can read from the file, how can we store frequency count against words. Simple, use a hash map. We read word from file, store in hash if it is not already there with count 1. If words is already in hash map, update the count by 1.

After this step, we have a hash with count of occurrence of each word. Now comes the challenging part:  how to find top n or most frequent words from this hash map. Mind you that hash map does not store elements in sorted or any order. 

Rule of thumb is to find top or least from collection of items, heaps are best bet. To find top N most frequently occurring words, let’s try heap. 
Which heap would be best?  We need to get a limited set, if we have free entry in that set till n words(as we need n top words). All further words have to pass a test before they enter the set. 

If new word is less than the least frequent word in the set, what can be said about this new word? Well, it cannot be in top n words right? 
If new word has frequency more than word with least frequency in set, new word should enter the set and  word with least frequency should be moved out.
What we just explained is typical use of min heap, as it give least element at the root. To find top n most frequent words in file, below is the algorithm.

Most frequent words in file : algorithm

  1. Take first N words appearing in map along with their count and create a min heap with these N words.
  2. One by one read words from hash and check if frequency of new word is more than least frequent word on heap, i.e word at root of heap.
  3. If yes, remove root and add new word in min heap. If not, continue with next word.
  4. When done with all words in hash, min heap will contain N most frequently occurring words in file.

Implementation

package com.company;

import javafx.util.Pair;

import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

/**
 * Created by sangar on 1.10.18.
 */
public class FrequentWords {

	public static HashMap<String, Integer> readFile(String fileName)
		throws IOException {
	HashMap<String, Integer> wordMap = new HashMap<>();

	Path path = Paths.get(fileName);
	try (Scanner scanner =  new Scanner(path)){
		while (scanner.hasNextLine()){
			String line = scanner.nextLine();
			if(wordMap.containsKey(line)) {
				wordMap.put(line, wordMap.get(line) + 1);
			}
			else{
				wordMap.put(line, 1);
			}
		}
	}
	return wordMap;
	}

	public static ArrayList<String> mostFrequentWords(String fileName, int n){
		ArrayList<String> topWords = new ArrayList<>();

		try {
			HashMap<String, Integer> wordMap = readFile(fileName);
			PriorityQueue<Pair<String, Integer>> pq =
				new PriorityQueue<>(n, (x,y) -> x.getValue().compareTo(y.getValue()));

			int i = 0;
			Iterator it = wordMap.entrySet().iterator();
			/*
				Get first n words on heap
			*/
			while(it.hasNext()){
				if(i == n) break;
				HashMap.Entry<String, Integer> entry =
					(HashMap.Entry<String, Integer>)it.next();
				pq.add(new Pair<>(entry.getKey(), entry.getValue()));
				it.remove();
				i++;
			}

			/*
				Check all other words, if anyone more than least
				remove the least and add the new word.
			*/
			for (String key : wordMap.keySet()){
				if(pq.peek().getValue() < wordMap.get(key)){
					pq.poll();
					pq.add(new Pair<>(key, wordMap.get(key)));
				}
			}
			while(!pq.isEmpty()){
				topWords.add(pq.poll().getKey());
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return topWords;
	}
	
	public static void main(String[] args){  
		System.out.println(mostFrequentWords("/home/sangar/Documents/test.txt", 3));
	}
}

Reading M words from file will require O(m) time, where as creating N element heap will take O(n). Also, scanning through all words and inserting them on to heap has complexity of O((m-n) log n). Overall complexity to find top n most frequent words in fileis O(m log m).


Next greater element in array

Next greater element in array

Given an array of integers, find next greater element for current element in array i.e. for each a[i], find minimum j so that a[j] > a[i] and j>i.

For the rightmost element, value will be -1. For any i, if there is no such j, then result for that too will be -1.
In simple terms, we need to find nearest greater number for each element in given array. For example:

Next greater element in array: Line of thought

Brute force method would be to scan array in two loops. For each element in array, scan remaining right side elements and find out the greater number. Complexity of code is O(n2). How can we do better and solve this in linear time?

What if while scanning the array, we keep track of all numbers for which greater number is yet not found. Idea is that whenever we see a number, check if there are elements which are already visited in array and yet there is no greater number assigned to them. If there are such elements, we check if current element is greater than them. If yes, then for all those numbers which are less than current element, next greater element will be current number. However, we have yet not find next greater number for current number, so put it back to list.

This list will be in decreasing order, as we will be removing all the numbers which are less than current number fro the list. They got current number as next greater number. All remaining numbers on list will be greater than current number. What will be the best data structure store this list? Stack, as we are interested in last element first.
This problem is very similar to stock span problem.

Next greater element in array : Algorithm

  1. Push first element on to stack
  2. While(!stack.empty && stack.peek() < current) stack.pop()
  3. Pair all popped numbers with current number
  4. If stack.top() > current or stack.empty(), stack.push(current)
  5. After scanning all elements in array, print all elements in stack paired with -1 as there is no greater element on right side of these elements.

Next greater element in array : Implementation

package com.company;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 19.9.18.
 */
public class NextGreaterElement {
    public static ArrayList<Pair<Integer, Integer>> nextGreaterElement(int[] a){

        Stack<Integer> s = new Stack();
        ArrayList<Pair<Integer,Integer>> nextGreater = new ArrayList<>();

        for(int i=0; i<a.length; i++){
            while(!s.empty() && a[i] > s.peek()) {
                nextGreater.add(new Pair<>(s.pop(), a[i]));
            }
            s.push(a[i]);
        }
        while(!s.empty()) nextGreater.add(new Pair<>(s.pop(), -1));
        return nextGreater;
    }

    public static void main(String args[]){
        int a[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98};
        ArrayList<Pair<Integer, Integer>> nextGreater = nextGreaterElement(a);

        System.out.println(nextGreater);

    }
}

Let’s workout an example: A = {5,6,3,35,23,6,8}. we start with empty stack = []. For the first element, we have empty stack, add 5 to stack. Now, stack = [5]

For next element 6, stack is not empty and element at the top of stack is less than 6. We will pop 5 from stack and create a pair. Output = {(5,6)}, we will push 6 back on to stack. stack = [6]

Next element is 3, which is less than top of stack, do nothing, and put the element on top of stack, stack = [6,3]

For 35, pop out 3 and 6 from stack and create pairs and add them to list. Output = {(5,6),(6,35), (3,35)}, add 35 to stack, stack = [35]

Next element is 23, which is less than top of stack, do nothing, and put the element on top of stack, stack = [35,23]

Again element 6, is less than top of stack, do nothing, and put the element on top of stack, stack = [35,23,6]

For 8, top of stack is less than 8, so pop and create pair and add to output. Output = {(5,6),(6,35), (3,35),(6,8)}, add 8 to stack, stack = [35,23,8]

Now there are not elements left, pop everything from stack and pair them with -1. Final output should be {(5,6), (6,35), (3,35), (6,8), (8, -1), (23, -1), (35, -1)}

Complexity of algorithm to find next greater element in array will be O(N) with extra space complexity of O(N) for stack.

Please share if there is something missing or wrong. If you are interested in taking personalized coaching for your interview preparations, please reach out to communications@algorithmsandme.com

Subarray with sum zero

Subarray with sum zero

Given an array of positive and negative integers, find a subarray with sum zero in that array. For example, in the array given below, there are two subarrays whose elements sum to zero.

subarray with sum zero
Input array
Array highlighted adds up to zero
subarray with zero sum

Brute force method to find subarray with sum zero will be to find all sub-arrays of the array and then add them individually to see if any subarray adds up to zero. There can be n * (n-1) subarrays for a given array of size n, so the complexity of brute force solution is O(n2).

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSumBrute(int[] a){
        int len = a.length;

        for(int i=0; i<len; i++){
            int  sum  = 0;
            for(int j=i; j<len; j++){
                sum += a[j];
                if(sum == 0){
                    return Arrays.copyOfRange(a,i,j+1);
                }
            }
        }
        return new int[0];
    }
}

Test cases

package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class SubarrayWithSumZeroTest {

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumBruteTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }

    @Test
    public void subarrayWithZeroSumBruteNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }

    @Test
    public void subarrayWithZeroSumBruteOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }
}

Find subarray with sum zero: thoughts

A subarray is a contiguous part of an array. Let’s say we find the sum of subarray starting at 0 and ending at any index i. So, T[i] represents the sum of subarray A[0..i].

What if we have two indices i and j; such that i< j and T[i] = T[j]. In this case, all the elements which are between index i and index j add up to zero and that is our subarray with sum zero.
Length of subarray with sum zero will be j-i+1.

Implementation

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSum(int[] a){

        int len = a.length;

        int [] T = new int[len];

        T[0] = a[0];
        for(int i=1; i<len; i++){
            T[i] = T[i-1] + a[i];
        }

        //Complexity of below code is O(n^2)

        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                if(T[i]== T[j]){
                    return Arrays.copyOfRange(a, i+1, j+1);
                }
            }
        }
        return new int[0];
    }
}

Test cases

package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class SubarrayWithSumZeroTest {

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

    @Test
    public void subarrayWithZeroSumNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

    @Test
    public void subarrayWithZeroSumOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

The complexity of the algorithm to find a subarray with zero sum in a given array of integers is O(n2) with an additional space complexity of O(n) to store sum till index i.

We can optimize it further by creating a hash of all the sums which we see while adding. When we add the index i to already calculated sum till index i-1, we check if the new sum is zero? If yes, then subarray from 0 to index i add up to zero. If there is already a sum present which is equal to the current sum then there is subarray with sum zero between index when we saw the sum last and current index.

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {

    public int [] findSubarrayWithZeroSumOptimized(int[] a){

        int len = a.length;

        HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();

        int sum  = 0 ;
        for(int i=0; i<len; i++){
            sum  += a[i];
            if(T.get(sum) != null){
                return Arrays.copyOfRange(a,T.get(sum)+1, i+1);
            }
            T.put(sum, i);
        }

        return new int[0];
    }
}

Test cases

package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class SubarrayWithSumZeroTest {

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumOptimizedTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

    @Test
    public void subarrayWithZeroSumOptimizedNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

    @Test
    public void subarrayWithZeroSumOptimizedOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

}

The complexity of this method is O(n) with additional space of O(n) in worst case.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free interview kit.

Constant time max operation on stack

Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too.

Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too.

Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too.

Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack.

Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens.

Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3.

Constant time max operation on stack : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> auxStack;

    public MaxStack() {
        stack = new Stack();
        auxStack = new Stack();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek();
        //Push on max stack only if max value is being changed.
        if (max <= x) auxStack.push(x);
        stack.push(x);
    }

    public int pop() {
        int returnValue = stack.pop();
        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return auxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

Complexity of implementation of constant time max operation stack is O(n) in terms of space, with O(1) time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is O(1) operation without moving any other element on stack.

However finding the node in doubly linked list itself is O(n) operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack.

Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack.

As for 3, same thing happens when 5 is pushed on to stack.

Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack.
constant time max operation on stack

After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack.

Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackDLL {
    private DoubleLinkedList dll;
    private Stack<ListNode<Integer>> auxStack;

    public MaxStackDLL() {
        auxStack = new Stack();
        dll = new DoubleLinkedList();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
        //Push on max stack only if max value is being changed.
        ListNode<Integer> newNode = dll.insertAtHead(x);
        if (max <= x) auxStack.push(newNode);
    }

    public int pop() {
        ListNode<Integer> returnValue = dll.deleteAtHead();

        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue.getData();
    }

    public int peekMax() {
        return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
    }

    public int popMax() {
        return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
    }
}

Doubly linked list class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class DoubleLinkedList {

    ListNode<Integer> head;

    public DoubleLinkedList(){
        head = null;
    }

    public boolean isEmpty(){
        return this.head == null;
    }

    public ListNode<Integer> insertAtHead(int data){
        if(this.isEmpty()) {
            this.head = new ListNode<Integer>(data);
            return this.head;
        }
        /*
            We are inserting node at head. So following things happen
            1. Create a new node.
            2. Set next of new pointer to current head.
            3. Set prev of head to new node
            4. Make new node as head of linked list
          */
        //First two steps are done here
        ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
        //Step 3.
        this.head.setPrev(newNode);
        //Step 4.
        this.head = newNode;

        return this.head;
    }

    public ListNode<Integer> deleteAtHead(){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<Integer> tempNode = this.head;
        this.head = this.head.getNext();
        this.head.setPrev(null);

        return tempNode;
    }

    public ListNode<Integer> deleteNode(ListNode<Integer> node){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        return node;
    }
}

ListNode class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class ListNode<T> {
    private T data;

    private ListNode<T> next;
    private ListNode<T> prev;

    public ListNode(T data){
        this.data = data;
        next = null;
        prev = null;
    }

    public ListNode(T data, ListNode<T> next, ListNode<T> prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    public ListNode<T> getNext(){
        return this.next;
    }

    public ListNode<T> getPrev(){
        return this.prev;
    }

    public void setPrev(ListNode<T> newNode){
        this.prev = newNode;
    }

    public void setNext(ListNode<T> newNode){
        this.next = newNode;
    }

    public T getData(){
        return this.data;
    }
}

Tester class is given below. Can you add more test cases to this?

package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackTest {


    MaxStackDLL tester = new MaxStackDLL();
    @Test
    public void popMaxTest() {

        tester.push(2);
        tester.push(3);
        tester.push(5);
        tester.push(1);

        assertEquals(5, tester.popMax());
        assertEquals(3, tester.popMax());
    }
}

Time complexity of push, pop and popMax is O(1). There is additional space requirement which is O(n).

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at communications@algorithmsandme.com

Stack data structure and applications

Stacks data structure

What is stack data structure? Stack is a dynamic data structure, where information is stack over one another. In common terminology, we use the stack with same meaning like stack of trays or stack of pancakes. Extend the concept of stack in real life, you remove the tray at the top before moving tray below it. So the tray which goes last on to stack, come off the stack first. This pattern is called as Last In First Out or LIFO.

For any data structure, three operations should be considered : How data can be added to it, how data can be removed from it and how data can be read from it? Let’s discuss these operations on stack one by one.

Operations on stack

Write operation on stack is commonly known as push. Push operation writes information on to top of the stack.Complexity of push operation is O(1) as no iteration is required.

Read operation is known as pop, where element at the top of stack is removed. Complexity of pop is also O(1).
stack data structure

Another operation which is commonly used is isEmpty(), this checks if there are any elements in stack at present.

What if you just want to check the top element of stack but do not want to remove it from stack? Then operation called peek() is for you. It reads the top element, however does not remove it from stack.

Since stack can dynamically increase and decrease in size based on push and pop operation, we need to keep track of the top of the stack.

Stack can be represented as recursive structure i.e if we remove the top of the stack, remaining N-1 element is again a stack.

Let’s take an example to see how push and pop operations on stack actually follow Last In First Out pattern.

stack data structure

Implementation of stack data structure

Stacks can be implemented in two ways, first where underlying data storage is an array and second where underlying storage is linked list. Refer difference between array and linkedlist to understand more that impacts stack implementation.

1. In Array based implementation of stack implementation, underlying data structure used is an array. We keep an extra variable (top) to keep track of number of elements present in stack at given time. When we push an element on to stack, increase the top. When we pop an element from stack, we decrease the top.

In this implementation, top being -1 represents empty stack and top equal to N-1, N being the size of array, represents stack full. Push and pop operations are of O(1) complexity.

Drawback of this implementation is that we need to define stack size statically at the compile time and changing it at runtime dynamically would be overhead.

#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void push(stack *ms, int item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}

//Get the element at the top of stack and remove it from stack
int pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}

//Get the element at the top of stack without removing it.
int peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}

//Function to check if stack is empty or not?
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}

2. In Linked List based implementation of stack implementation, underlying data structure used is linked list. Every node in the linked list represents an element in stack. Every push operation adds a node at the head of linked list and every pop operation removes a node from head of the linked list.

In this implementation too, push and pop operations are of O(1) complexity. Also stack can grow as much as required. Head being NULL represents empty stack.

Drawback is we need to store 4 bytes extra as next pointer for each element.

#include <stdio.h>

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
} Node;

/* Create a node of linked list */
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
 
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
    Node *newNode  = createNode(data);
    newNode->next = *headRef;
    *headRef  = newNode;
}

/* This function removes node from the head of linked list */
Node * pop(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    Node * poppedNode = *headRef;
    *headRef = (*headRef)->next;
    return poppedNode;
}

/* This function return node at the head of linked list */
Node * peek(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    return (*headRef);
} 

int isEmpty(Node **headRef){
    return (*headRef == NULL);
}

Stack Overflow

You must have heard the term stack overflow. Why does it occur and how does it relates to stack data structure?
Stack supports function call paradigm in programming languages. When a function in your program calls another function (which can be the same function in case of recursion), program management module in operating system stores quite a few things to have safe return. This includes : parameters passed to function, return values, return pointers. As you go deep into function calls, one function calling second, then second calling third and so on, each of this successive call takes a frame of system stack as explained above. Depending on the size of information you are putting on stack frame in each call, sooner or later, stack will be full, as it has limited memory allocated in kernel.

Now when you try to add one more frame because you are calling another function, there is no space. That’s when stack overflow happens.

Why do you think function call information is store on stack and not on any other data structure? Let’s say your program calls function A from function B, which in turn was called from function C. When you are returning from function A, you want to return to calling address in function B and not function C. So, you want to return back in reverse order of calling sequence, LIFO, that why stack is best data structure.

It is recommended to implement production code in iterative way rather than recursive using application level stacks. As application stack is allocated from heap, it can grow much bigger than kernel stack. Also, you can select what to put on stack. If you look at iterative preorder traversal, iterative postorder traversal interview problems, they are nothing but to test your knowledge of stack data structure. To read more on stack overflow, please refer : stack overflow

Application of stack : browser back button

Let’s solve a problem and see how stack data structure can be used to solve problems. Problem statement is : Implement back button on browser. When you click on back button, you go to previous site you visited. You press it again, than you go to site prior to it and so on.

Do you see application stack here? When you go back, you want to land on the last site you visited. What pattern is this? Of course, it last in first out which can be implemented using stack.
So idea is to whenever you move to new site or page, current page is added to stack. If you press back button, top of the stack is popped and return to you as current page. If you press again, top of the stack contains now the page you visited before current page, so land there.

browser back button using stack

There can one more complexity added to this problem, which is you want to implement forward button too. In that case, whenever you pop out a page from back stack, put it into a new stack called forward stack. Can you run through some examples and see if that actually works?

Please share if there is something wrong or missing. If you are interested in taking personal coaching by our experienced teachers, please reach out to us at communications@algorithmsandme.com

Merge k sorted arrays

Merge k sorted arrays

Given k sorted arrays each having n elements, merge k sorted arrays into one n*k element array in sorted order. For example, given 3 arrays are as below

merge k sorted arrays
merge k sorted arrays

Result array should be like

Merge k sorted arrays

Merge k sorted arrays

Since all the input arrays are sorted, the first element in result array will be among the first elements of input arrays. How can we find the minimum among all the elements plucked from the first index of each array ? Easy, take those k elements (there are k arrays, so k first elements) and build a min heap. The root of the min heap the least element among the first elements of all arrays, so it will be the first element in the result array.

Once, we add the first element into the result array, we have to find the second element. Second element can be from the set of first elements of all input arrays except one array from which the first element of result array was added. So, we will take second element of that array.

In order to know which array gave the minimum element at a particular time, we will store additional information of about array and index at which minimum element was.

If i represents the array number, and j represents the index of the minimum number in heap in ith array, then we add (j+1)th element to the min heap next and re-heapify. If j goes out of bound for ith array, we take min heap with k-1 size and go on, till we have no elements left in heap.

Follow the procedure for (n-1)*k times. When all array elements are processed, result array will be in the sorted array.

Merge k sorted arrays: algorithm

  • Build min heap with the first element of all k arrays.
  • Pick the root of min element and put it in the result array.
  • If there are remaining elements in the array,  put next element at the root of min heap and heapify again
  • If all elements are already of an array are processed, reduce the size of min heap by 1.
  • Repeat step 2, 3 and 4 till min heap is empty.

Merge k sorted arrays: implementation

package com.company;

import java.util.PriorityQueue;

/**
 * Created by sangar on 2.12.18.
 */
public class MergeKSortedArrays {
    private class HeapNode{
        public int arrayNum;
        public int index;
        public int value;

        public HeapNode(int arrayNum, int index, int value){
            this.arrayNum = arrayNum;
            this.index = index;
            this.value = value;
        }
    }

    public int [] mergeKSortedArrays(int[][] arrays){

        if(arrays == null) return null;

        PriorityQueue<HeapNode> minHeap =
			new PriorityQueue<>(arrays.length,
                (HeapNode a,HeapNode b)-> a.value - b.value);

        int size = 0;
        for(int i =0; i<arrays.length; i++){
            size += arrays[i].length;
        }
        int[] result = new int[size]; // k * n

        //add first elements in the array to this heap
        for(int i=0; i<arrays.length; i++){
            minHeap.add(new HeapNode(i, 0, arrays[i][0]));
        }

        //Complexity O(n * k * log k)
        for(int i=0; i< size; i++){
            //Take the minimum value and put into result
            HeapNode node = minHeap.poll();

            if(node != null){
                result[i] = node.value;
                if(node.index + 1 < arrays[node.arrayNum].length) {
                    //Complexity of O(log k)
                    minHeap.add(new HeapNode(node.arrayNum,
                           node.index + 1,
                           arrays[node.arrayNum][node.index + 1]));
                }
            }
        }
        return result;
    }
}

Test cases

package test;

import com.company.MergeKSortedArrays;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MergeKSortedArraysTest {

    MergeKSortedArrays tester = new MergeKSortedArrays();

    @Test
    public void mergeKSortedArraysTest() {

        int[][] input  ={
            { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }
        };

        int[] expectedOutput = {1,2,3,4,5,6,7,8,9,10,11,12};

        int [] output = tester.mergeKSortedArrays(input);

        System.out.println(Arrays.toString(output));
        assertEquals(Arrays.toString(expectedOutput), 
					Arrays.toString(output));
    }

    @Test
    public void mergeKSortedArraysWithUnequalSizeTest() {

        int[][] input  ={
                { 1, 2 }, { 5, 6, 7}, { 9, 10, 11, 12 }
        };

        int[] expectedOutput = {1,2,5,6,7,9,10,11,12};

        int [] output = tester.mergeKSortedArrays(input);

        System.out.println(Arrays.toString(output));
        assertEquals(Arrays.toString(expectedOutput),
			Arrays.toString(output));
    }

    @Test
    public void mergeKSortedArraysWithNullTest() {

        int [] output = tester.mergeKSortedArrays(null);

        assertEquals(null, output);
    }
}

Complexity of code to merge k sorted arrays is O(n * k * log k) along with space complexity of O(k).

Please share if there is something wrong or missing. If you are preparing for an interview, please sign up to receive interview preparation kit for free.

Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf