Find pivot element in a sorted and rotated array

Problem Statement

Suppose we have a sorted array, and now we rotate it N times, find the pivot element. The pivot element would be the largest element. Also, can you calculate N?

Clues

  • Solution should be O(log N) in time and O(1) in space.
  • Can you think of  a binary search based solution where you keep comparing the middle element with the last element?

Solution

The pivot element is basically, the largest element in an array. For a sorted and rotated array, it might be somewhere in between. We can solve this in O(log N) time, through a divide-and-conquer approach, which is similar to peak finding algorithm. We will have the lower limit (low) and the upper limit (high) from which we will calculate the ‘mid’. Now, we must address a few cases –

  • arr[mid] > arr[high] – If the mid element is greater than the last element, then the pivot should be in the second half of the array. Why is this so? This is actually because it is a sorted and rotated array. You may not understand this at first, but think of the values of the elements in the array as a histogram. Try to understand the picture below, I’m sure you can figure out why this happens –
    Pivot Element - Case 1

    Pivot Element – Case 1

  • arr[mid] < arr[high] – If the mid element is less than the last element, then the pivot should be in the first half of the range.
    Pivot Element - Case 2

    Pivot Element – Case 2

  • If mid element is a peak – If the mid element satisfies the property of the peak element (not lesser than its neighbors), then, it is the pivot.
If we can put these conditions, and handle the trivial cases, we can compute the pivot element. The number of times the array is rotated would be (IndexOfPivotReturned + 1).

C
// A Divide-and-Conquer approach to find the pivot (highest) element in
// a sorted rotated array - returns the index of the pivot -> O(log N)
int peakElement(int arr[], int low, int high, int lowerBound, int upperBound)
{
	int mid = low + (high - low) / 2;
	
	if (mid == lowerBound) {
		if (mid == upperBound) {
			// Only 1 element
			return mid;
		} else if (arr[mid] >= arr[mid + 1]) {
			// Pivot is the greater element
			return mid;
		}
	} else if (mid == upperBound) {
		if (arr[mid] >= arr[mid - 1]) {
			// Pivot is the greater element
			return mid;
		}
	} else {
		if (arr[mid] >= arr[mid + 1] && arr[mid] >= arr[mid - 1]) {
			// Mid value is the pivot
			return mid;
		} else if (arr[mid] > arr[high]) {
			// The Pivot is in the second half
			return peakElement(arr, mid + 1, high, lowerBound, upperBound);
		} else if (arr[mid] < arr[high]) {
			// The Pivot is in the first half
			return peakElement(arr, low, mid - 1, lowerBound, upperBound);
		}
	}
	
	return -1;
}

Kth smallest element in an array

Problem Statement

Given an unsorted array of N elements, find the kth smallest element. kth smallest element is the element at index k if the array were sorted.

Clues

  • Solution should be O(N) in time and O(1) in space.
  • Can you think of a divide-and-conquer based solution?
  • Can you apply Quicksort’s partitioning logic here?

Solution

This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a very useful divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array. A step-by-step version of Quickselect is –

  •  Calculate the middle element for the given range.
  • Place all the elements greater than the mid element to its right.
  • Place all the elements lesser than the mid element to its left.
  • If ‘k’ is less than the index of the middle element, then recursively call Quickselect on the left half of the range.
  • If ‘k’ is greater than the index of the middle element, then recursively call Quickselect on the right half of the range.

Code

C
// Quick Select procedure to search for
// the kth smallest element in O(N) time.
void quickSelect(int arr[], int low, int high, int k)
{
    if (high - low < k) {
        // A single element is 
        // considered to be sorted
        return;
    }
     
    int mid = low + ((high - low) / 2);
     
    // Put the pivot at the last
    int temp = arr[mid];
    arr[mid] = arr[high];
    arr[high] = temp;
     
    int pivot = arr[high];
    int i = low;
    int j = high - 1;
     
    // The partition
    while (j >= i) {
        if (arr[j] < pivot && arr[i] > pivot) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
             
            ++i;
            --j;
        } else if (arr[j] < pivot && arr[i] <= pivot) {
            ++i;
        } else if (arr[j] >= pivot && arr[i] > pivot) {
            --j;
        } else if (arr[j] >= pivot && arr[i] <= pivot) {
            ++i;
            --j;
        }
    }
     
    // Bring the pivot back to its
    // appropriate place
    temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
     
    if (k >= i) {
        quickSelect(arr, i + 1, high, k);
    } else {
        quickSelect(arr, low, i, k);
    }
}

Intersection of two sorted arrays

Problem statement

Given two sorted arrays, find the intersection (elements present in both arrays).

Clues

  • Solution must be O(M + N) in time and O(min(M, N)) space.
  • Can you apply merge sort’s merging logic here?

Solution

This is simple, we can do this in O(M + N) time, where M and N are the array lengths. What we will do here is similar to the “merging” step in merge sort. We will traverse the two sorted arrays simultaneously. Let’s say the first array, A, is indexed by i, and the second array, B, is indexed by j, then,

  • A[i] == B[j] – then add it to the intersection.
  • A[i] > B[j] – then increment j.
  • A[i] < B[j] – then increment i.

In terms of space, it will cost us as much as the size of the intersection, which is minimum of M and N. This isn’t necessarily a tough question, but your impression would take a big blow if you start overthinking this and fail to answer this.

Code

Java
public static ArrayList<Integer> getIntersection(int[] A, int[] B) {
    // Add interesting elements to this collection
    ArrayList<Integer> intersection = new ArrayList<>();
 
    int i = 0, j = 0;
 
    while (i != A.length && j != B.length) {
        if (A[i] == B[j]) {
            // If both are equal, add to intersection
            intersection.add(A[i]);
            ++i;
            ++j;
        } else if (A[i] > B[j]) {
            // Increment index to second array
            ++j;
        } else {
            // A[i] < B[j]
            // Increment index to first array
            ++i;
        }
    }
 
    return intersection;
}

Element in an array which appears once while other elements appear twice

Problem Statement

Given an array of numbers where all numbers appear twice except for one number which appears only once, find that number.

Clues

  • Solution should be O(N) in time and O(1) in space.
  • Use bit operations.

Solution

XOR of two same numbers is zero. So, if we take the XOR of all numbers in the array, the numbers which appear twice will get cancelled and in the end the number which is left would be our number which had appeared only once. Example –

  • 2 ^ 2 = 0
  • 2 ^ 2 ^ 3 = 3
  • 2 ^ 3 = 1
  • 1 ^ 2 = 3
  • 1 ^ 3 = 2
  • 2 ^ 3 ^ 2 = 3
  • 2 ^ 3 ^ 3 = 2

This solution would be O(N) in time and O(1) in space.

Code

C
int findNonDuplicate(int arr[], int n)
{
    int xorVal = 0, i;
     
    // XOR all the elements
    for (i = 0; i <span class="mce_SELRES_start" data-mce-type="bookmark" style="display: inline-block; width: 0px; overflow: hidden; line-height: 0;"></span>< n; ++i) {
        xorVal ^= arr[i];
    }
     
    return xorVal;
}

Artificial Intelligence – MiniMax Algorithm

Hello people! In this post we will look at one of the most basic Artificial Intelligence algorithm, the MiniMax algorithm. MiniMax algorithm is used to implement basic AI or game logic in 2 player games. The most common scenario is implementing a perfect Tic-Tac-Toe player. So, in this article we will look at how to implement it.

Definition –

Given that two players are playing a game optimally (playing to win), MiniMax algorithm tells you what is the best move that a player should pick at any state of the game. So, the input to MiniMax algorithm would be –

  1. State of the game.
  2. Whose turn it is.

And the output would be the best move that can be played by the player given in the input.

Idea of MiniMax Algorithm –

In the game of Tic-Tac-Toe, there are two players, player X and player O. Now imagine there’s a scoreboard which displays a huge number called “score”, and –

  1. If X wins, the score increases by 10.
  2. If O wins, the score is decreased by 10.
  3. If it is a draw, then the score remains unchanged.

So now, the bigger the number score has, the better it is for X, which means X will try to maximize score as much as possible. Similarly, the lesser the score, the better it is for O, so O will try to minimize the score as much as possible.

To understand this better, imagine you are player X and this is the current state of your game –

Artificial Intelligence - MiniMax algorithmSo if you are in state 1 (from the above diagram), you have 3 possible moves which lead to state 2, 3 and 4. For these moves the scores are –

  • +10 if you choose state 2.
  • 0 if you choose state 3 because it will be a draw if Player O is playing optimally.
  • -10 if you choose state 3.

So conceptually we know that player X must choose the winning move. This is done programmatically bu choosing the move which will return the maximum score. So, X will always try to maximize the score and will always choose that move which will fetch X the maximum score. Thus, in the above scenario X chooses the move which goes to state 2.

Now, to make sure you understand both sides of this algorithm. Let us take the same state as above and let us say it is O’s turn now and not X’s. Can you draw a state diagram which will depict all the possible moves and the scores which will be returned by playing them? You can! Just pause here for a moment and try to draw the state diagram for the above game, assuming it is player O’s move.

You should get a diagram like this –

Artificial Intelligence - MiniMax algorithmDid you get a diagram like this? Good job if you did 😉 . Player O has 3 possible moves and the scores are –

  • -10 if you choose to go to state 2.
  • -10 if you choose to go to state 3.
  • +10 if you choose to go to state 4.

Player O will always try to minimize the score, so player O must select a move which will either lead to state 2 or 3 to win.

Writing code for MiniMax algorithm –

Writing code for MiniMax algorithm is not very difficult, but you may not get it in the first try so I’ll help you out. Firstly, have a clarity on the smaller pieces of logic and write methods for them first. You will need these 3 helper methods for your code –

  1. printGame(game) – which prints the state of Tic-Tac-Toe game.
  2. hasPlayerWon(game, player) – which tells if the given player has won the given Tic-Tac-Toe game.
  3. score(game) – which returns +10 if player X has won, -10 if player Y has won, 0 otherwise.

So now you have a little clarity over the smaller pieces, code them first. Now, you are ready to write the MiniMax algorithm method. It is a recursive method which takes in 2 inputs –

  • the state of the game
  • information on which player’s turn it is.

It will need to return –

  • max/min score which can be achieved for the given player for the given game state.
  • best move which can be played by given player.

We can make a new class to return all the information we need. So, our MiniMax algorithm will look like –

(score, bestMove) minimaxAlgorithm(game, isXTurn):
    if player X has won:
        // score is 10, no best move in this case
        return (score = 10, move = none)
    if player O has won:
        // score is -10, no best move in this case
        return (score = -10, move = none)

    bestMove = (none, none)

    foreach emptySpace in game:
        game[emptySpace] = isXTurn ? X : O
        currentMove = (
                        score = minimax(game, !isXTurn).score,
                        move = emptySpace
                      )
        
        if currentMove is better than bestMove:
            bestMove = currentMove

        game[emptySpace] = emptySpace

    if no bestMove was found:
        // score is 0, no best move in this case
        return (score = 0, move = none)

    return bestMove

With your new clarity over the helper methods and the pseudocode, try to write the code for MiniMax algorithm. When in doubt come back and read the MiniMax algorithm theory and the implementation tips. Remember, you are trying to write the code for an ideal Tic-Tac-Toe player here, so you need to write the starter code for simulating a 2-player Tic-Tac-Toe game.
Try it on your own, it will be fun to create a game. If you get stuck, you can refer to my code –

The above implementation is a pretty raw. It doesn’t have checks like checking if user has input an empty cell or not. I trust you can fix all those loopholes. If you do, in the end you have an unbeatable Tic-Tac-Toe player! Congrats on taking your first step to build your dream AI! 😀

Some awesome resources –

Keep practicing! Happy Coding! 😀

Java Tutorials – Inheritance

Hello, people…! In this post, we will explore the next part of object oriented programming in Java which is Inheritance.

Inheritance

Inheritance is a feature of object oriented programming which allows a class to be created from an existing class. More formally, inheritance is the process by which the new child subclass automatically includes any public or protected primitives, objects or methods defined in the parent class.
Let us see what is means. In Java, we implement inheritance by using the extends keyword at the time of class declaration. Go through the cod snippet below carefully –

class ParentClass {
    int var;
}

class ChildClass extends ParentClass {
    // empty
}

public class InheritanceDemo {

    public static void main(String[] args) {
        ParentClass parent = new ParentClass();
        ChildClass child = new ChildClass();

        System.out.println(parent.var);
        System.out.println(child.var);
    }

}

Important things to note are –

  • ChildClass inherits ParentClass using the keyword extends.
  • When ChildClass inherits the ParentClass, all the public/protected/default methods and variables are automatically available to the ChildClass.

So, when a ChildClass inherits (or extends) a ParentClass it gets a few resources from the ParentClass. Now let us see exactly what get’s inherited and what does not.

What is inherited?

  • public or default variables.
  • public or default methods.
  • abstract methods (remember abstract methods cannot be private).
  • public or default static methods.

What is not inherited?

  • constructors are not inherited.
  • private variables.
  • private methods.
  • private static methods.

this reference

Let’s say you have a class like this –

class Point {
    int x, y, z;

    public Point(int xValue, int yValue, int zValue) {
        x = xValue;
        y = yValue;
        z = zValue;
    }
}

Now, the constructor’s formal parameter names are descriptive, but a little redundant. In some cases, we would want the name of the formal parameter (xValue) to be same as that of the instance variable (x). What would happen if we did this?

class Point {
    int x, y, z;

    public Point(int x, int y, int z) {
        x = x;  // Assignment to itself
        y = y;
        z = z;
    }
}

It is of no use because the x inside the method is the formal parameter but not the instance variable of Point class. This happens because a local variable takes precedence over a global variable. So, how do we reference the instance variables where the formal parameters have the same name? We use this keyword! Take a look at the constructor below –

class Point {
    int x, y, z;

    public Point(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

We use this reference to refer to the instance variables, or, more formally, this reference is used to refer to the current instance. By current instance we imply the instance variables and methods. So, in the above code snippet, the instance variables are initialized to the formal parameters of the constructor.

So now that you know what this reference can you guess the output of the following code snippets?

Code SnippetSnippet Output
class Point {
    int x, y, z;

    public Point(int x, int y, int z) {
        x = x;
        this.y = y;
        z = this.z;
    }
}

class InheritanceDemo {

    public static void main(String[] args) {
        Point p = new Point(10, 20, 30);

        System.out.println(p.x);
        System.out.println(p.y);
        System.out.println(p.z);
    }

}
0
20
0

I hope you got the answer right! Let us look at the three statements in the constructor. The first statement assigns the formal parameter x to itself. The second statement is the right way of initializing, and hence y outputs 20. The third statement assigns the instance variable z (value is 0 currently) to the formal parameter z (value changed from 30 to 0).

super reference

Let’s say we have two classes, Doctor and ExpertDoctor. A Doctor works on a few things only whereas an ExpertDoctor does a little more than what a Doctor can do. The classes may look like –

class Doctor {
    public void work() {
        System.out.println("Check blood pressure");
        System.out.println("Check haemoglobin levels");
        System.out.println("Check glucose levels");
    }
}

class ExpertDoctor extends Doctor {
    public void work() {
        System.out.println("Check blood pressure");
        System.out.println("Check haemoglobin levels");
        System.out.println("Check glucose levels");
        System.out.println("Check liver functioning");
        System.out.println("Check heart functioning");
    }
}

Well, an ExpertDoctor IS A Doctor, so ExpertDoctor inherits Doctor class. But clearly, we are not getting any advantage here. The work() in ExpertDoctor does a little more than work() in Doctor. Wouldn’t it be nice if we could call work() method of Doctor class inside ExpertDoctor class? Then we would have to write only the additional work done by the ExpertDoctor. This can be achieved by using super reference!

class Doctor {
    public void work() {
        System.out.println("Check blood pressure");
        System.out.println("Check haemoglobin levels");
        System.out.println("Check glucose levels");
    }
}

class ExpertDoctor extends Doctor {
    public void work() {
        super.work();
        System.out.println("Check liver functioning");
        System.out.println("Check heart functioning");
    }
}

class InheritanceDemo {

    public static void main(String[] args) {
        ExpertDoctor doc = new ExpertDoctor();

        doc.work();
    }

}

So, we call work() method of Doctor class using super keyword. The output for the above code is –

Check blood pressure
Check haemoglobin levels
Check glucose levels
Check liver functioning
Check heart functioning

super is a keyword used to reference a member defined in the parent class and can be used throughout the child class.

this() constructor call

Can constructors be overloaded? Yes! You can have multiple overloaded versions of a constructor. Example –

class Time {
    int seconds, minutes, hours;
    
    // Contstructor 1
    public Time(int seconds) {
        this.seconds = seconds;
    }
    
    // Constructor 2
    public Time(int seconds, int minutes) {
        this(seconds); // Calls constructor 1
        this.minutes = minutes;
    }
    
    // Constructor 3
    public Time(int seconds, int minutes, int hours) {
        this(seconds, minutes); // Calls constructor 2
        this.hours = hours;
    }
}

In the above example, we several constructors each of which initialize a certain set of instance variables. We can use this() to call a constructor from another constructor.

super() constructor call

Similar to this(), Java has super(). It is used to call the parent class constructor. Example –

class Time {
    int seconds, minutes, hours;
    
    // Constructor 1
    public Time(int seconds) {
        this.seconds = seconds;
    }
    
    // Constructor 2
    public Time(int seconds, int minutes) {
        this(seconds); // Calls constructor 1
        this.minutes = minutes;
    }
    
    // Constructor 3
    public Time(int seconds, int minutes, int hours) {
        this(seconds, minutes); // Calls constructor 2
        this.hours = hours;
    }
}

class Date extends Time {
    int day, month, year;
    
    // Constructor 4
    public Date(int seconds, int minutes, int hours, int day) {
        super(seconds, minutes, hours); // Calls constructor 3
        this.day = day;
    }
    
    public Date(int seconds, int minutes, int hours, int day, int month, int year) {
        this(seconds, minutes, hours, day); // Calls constructor 4
        this.month = month;
        this.year = year;
    }
}

Rules about constructors –

  • The first line of the constructor must be a call to another constructor of the same class, or a call to the constructor of parent class.
  • If you don’t make a constructor call in the first line, Java automatically adds super() to the first line. So, if there’s no constructor in super class that matches to super(), a compilation error occurs.
  • If you don’t want Java to add a super() automatically in the first line, you must write your own constructor call explicitly.

I hope my post gave you a fair understanding of what inheritance is. If you have any doubts, feel free to comment them! Keep practicing! Happy Coding!! 😀

Compressed Trie Tree

Hello, people! In this post, we will discuss a commonly used data structure to store strings, the Compress Trie Tree, also known as Radix Tree or Patricia (Practical Algorithm to Retrieve Information Coded in Alphanumeric) Tree. If you remember, the problem with a Trie Tree is that it consumes a lot of memory. So, due to its memory consumption, developers prefer using a compressed trie tree to get the same functionality at the same runtime complexity in memory-critical situations such as in android apps.

“Compress”-ing the tree

Now, the idea of the compressed trie tree is to convert long chains of single-child edges to one single edge. Example, suppose we have two words “facebook” and “facepalm” in our regular trie tree, it would look like –

Trie Tree

It’s a pretty long one, isn’t it? Now, how about this one below?

compressed trie tree

This one surely looks a lot compact! This is the compressed trie tree. As you can see what we do here is to make long chains of single-child edges into one edge. Unlike a regular trie tree, in a compressed trie tree, the edge labels are strings.

Node in Compressed Trie Tree

For a regular trie tree, our tree node looked something like this –

class Node {
    Node[] children = new Node[26];
    boolean isWordEnd;
}

So, in every node, we had an array of references. The first references corresponded to ‘a’, the second to ‘b’, and so on. So, essentially, we had a mapping of alphabets to references. We had a way of saying, “An edge ‘a’ is denoted by this particular element in the array of references”. Now, in a compressed trie tree, the edges are labeled by strings. Now, we need a way of saying, “An edge ‘face’ is denoted by this particular element in the array of references”. To accomplish this, we re-design our tree node as follows –

class Node {
    Node[] children = new Node[26];
    StringBuilder[] edgeLabel = new StringBuilder[26];
    boolean isEnd;
}

So, what we did is that we added an additional array of Strings along with the array of references. Now edgeLabel[0] will denote the string starting with ‘a’, edgeLabel[1] will denote the string starting with ‘b’, and correspondingly, children[0] will denote the edge with the label edgeLabel[0].

Example, in the above diagram, the root node will have edgeLabel[5] = “face” and children[5] will point to the internal node. The internal node will have edgeLabel[1] = “book” and children[1] will point to the leaf node which will denote the occurrence of the word “facebook”. The same internal node will also have edgeLabel[15] = “palm” and children[15] will point to the leaf node which will denote the occurrence of the word “facepalm”. The rest of the values of edgeLabel and children in the internal node will be null.

The above code is written in Java. For Java, it is much better to use StringBuilder rather than String because we would be doing a lot of string manipulation. Using String will heavily slow down your program. If you are not familiar with StringBuilder, you can refer to my post.

insert() operation

All operations in the compressed trie tree are similar to what we would do in a regular trie tree. Insert operation is the one which will differ the most. In the insert operation, we need to take care of a few cases, they are –

  1. Inserting new node for a new word – This occurs when the starting character of the word is new and there’s no edge corresponding to it. This may occur at root, or after traversing to an internal node.compressed-trie-tree-4
  2. Inserting a prefix of an existing word – Inserting prefix into compressed trie tree
  3. Inserting a word which has a partial match to an existing edge – This occurs when we are trying to insert “this” when “there” is already inserted into the tree. Remember that “there” can have further children too, like if “thereafter” and “therein” are already inserted.breaking words during compressed trie tree insertion

So, for these cases, we would have to break the existing word or the newly inserted word accordingly. The faster we perform these string operations, the faster the insert operation will be.

search() operation

Searching in a compressed trie tree is much like searching. Here, instead of comparing a single character, we compare strings. The following cases will arise –

  • The string we want to search does not exist. Example, searching for “owl” when the tree only has “crow” in it.
  • The string we want to search exists as a prefix. Example, searching for “face” when the tree only has “facebook”.
  • Only the prefix of the target string exists. Converse of the previous case. Searching for “facebook” when the tree only has “face”.
  • The string we want to search matches partially with an existing string. Example, searching for “this” where the tree only has “there”.
  • Another case is when the edge label fully matches to the starting portion of the string. Example, searching for “thereafter” when “thereafter” and “therein” exist in the tree. For this, after a full match with “there”, we traverse to the node which corresponds to that label and then resume our search (searching for “after”).

If we are able to fully traverse the tree via the target string and arrive on a tree node, we check if that node is a word ending or not. If yes, we return true or, we return false. For rest of the cases, return false.

startsWith() operation

The startsWith() operation is a popular operation performed on the compressed trie tree which checks if there’s any word in the tree which starts with the target word. This method would be exactly as the searching method. The minor change with the search operation would be, in this operation, we will just check if we are able to fully traverse the tree via the target string and arrive on a node (which may be the root). If we can we return true, regardless of whether the current node is a word ending or not. This is because, even if it is not a word ending, its children will lead to a node which would be a word ending.

Printing the compressed trie tree

For each edge traversed, add its label to a variable and recursively do this for the child node. While traversing another edge, remove the previously added label and add the new label of the new edge traversing. Print the variable only if the current node is a word ending.

This recursive method should print all the words in the compressed trie tree in a lexicographical order.

Code

Start with your existing trie tree code, modify the node definition and then work on the insert method cases. Once you get the insert correctly, then the rest will work out easily. For the insert cases, you just have to do the string operations and change the references carefully. Try to code those cases. Come back and have a look at the diagrams if you need to.

You can check your code’s correctness with LeetCode’s Implement Trie problem. Try to solve that question using a compressed trie tree. Once you solve it, try to reduce the runtime of your program.

You can refer to my code if you get stuck. 🙂

    

This is the Java implementation. I will update this post with the C/C++ implementation soon.

In terms of runtime complexity, compressed trie tree is same as that of a regular trie tree. In terms of memory, a compressed trie tree uses very few amount of nodes which gives you a huge memory advantage especially for long strings with long common prefixes. In terms of speed, a regular trie tree would be slightly faster because its operations don’t involve any string operations, they are simple loops.

I hope my post has demystified everything regarding a compressed trie tree. Tutorial and code for a compressed trie tree are hard to find. I hope my post saved you the effort of finding further tutorials. Do comment below if you have any doubts. Keep practising! Happy Coding!! 😀

Jump Search Algorithm

Hello, people…! In this post, we will discuss a new search algorithm, Jump Search, which searches for an element in a sorted array in O(√N) time. It is slower than binary search, then why learn it? What if the interviewer purposely asks you to write a search algorithm with O(√N) worst case complexity? You would be banging your head to cook up a new algorithm 😛 . Anyways, it’s fun learning new stuff, isn’t it?

Algorithm

Imagine you are given a sorted array, and you are applying linear search to find a value. Jump Search is an improvement to this scenario. Instead of searching one-by-one, we search k-by-k. Let’s say we have a sorted array A, then jump search will look at A[1], A[1 + k], A[1 + 2k], A[1 + 3k] … and so on.

As we keep jumping, we keep a note of the previous value and its index. Once we get a situation where A[i] < searchValue < A[i + k], then it means the value we want is in between the previous jump ends. So now we could simply perform a linear search between that A[i] and A[i + k].

Jump Search

Sound too boring? Here’s where things get interesting! How will we know the most optimal value of the jump size?

Optimal Jump Size

If we try to write down the complexity of the algorithm we described above.


\frac{n}{m} + m - 1
Now, let’s see for which value of ‘m’ does this expression have a minimum. To do this we differentiate with respect to ‘m’ and equate it to 0


\frac{n}{ -m^{2} } + 1 = 0 \newline \newline  n = m^{2} \newline \newline  m = \sqrt{n}
So, the optimal jump size is √N.

Code

It is a pretty simple algorithm to code. Try it by yourself. You can refer to my code below if you get stuck 🙂 .

CC++JavaPython
    
    
    
    

Faster Jump Search

How can we make this version of jump search faster? A few people might have guessed it by now! 😉 In the above algorithm, once we find the jump ends which contains the value we need, we are performing a linear search. But we could perform another jump search between these two jump ends! And then recursively perform jump search until we are left with only one element.

Implementing this version is more challenging. Firstly, you need to modify your above method to something which looks like this –

public Pair jumpSearchUtil(int[] arr, int val, int low, int high) {
    // return jump ends if condition meets
    // return null or a -1 otherwise
}

We must return the i and j between which the value is found or return null. And then call this from another method jumpSearch() which keeps calling jumpSearchUtil() until the jump interval has only 2 elements or it returns a null. We will need to return 2 values, the left end and the right end of the jump. So, we will use a structure in C, or a class in Java.

Try to code this version of Jump Search algorithm. If you get stuck, you can use my code below as a reference –

CJava
    
    

This optimised version has the following complexity –


\sqrt{N} + \sqrt{\sqrt{N}} + \sqrt{\sqrt{\sqrt{N}}} + ... + 1

This is still O(√N) in the worst case. But it is much faster because, in the previous version, the complexity was √N + √N, which made it O(√N), but here the additional terms have very low values.

I hope you’ve understood about the jump search algorithm. If you did, let me know by commenting! Keep practising! Happy Coding! 😀

Dynamic Programming – Edit Distance

Hello people..! In this post, we will see another dynamic programming based problem, finding the minimum edit distance between two strings.

Problem – Given two strings A and B, we need to find the minimum number of operations which can be applied on A to convert it to B. The operations are –

  • Edit – Change a character to another character.
  • Delete – Delete a character.
  • Insert – Insert a character.

Normally I would take a brute force solution and reduce it to a dynamic programming solution, but in this case I’m not sure how I can do that 😛 . So, I will straight away explain the dynamic programming solution in the best way I can.

Example

Let’s take an example. Let the string A = “this”, and let string B = “there”. Now we will perform a very simple pen-and-paper exercise. Please draw the chart given below in your rough notes –

Edit distance matrix

The Y axis denotes the source string A and the X axis denotes the target string B.

  • Empty cell at 1st row, 1st column denotes the situation when A = ∅ and B = ∅. The edit distance would be 0.
  • Empty cell at 1st row, 2nd column denotes the situation when A = ∅, B = “t”. We would need 1 insertion to convert A to B. Here, the answer is 1.
  • Empty cell at 1st row, 3rd column denotes the situation when A = ∅, B = “th”. We would need 2 insertions to convert A to B. Here, the answer is 2.
  • Empty cell at 1st row, 6th column denotes the situation when A = ∅, B = “there”. We would need 5 insertions to convert A to B. Here, the answer is 5.

This is the trivial case when A = ∅. The other trivial case is when B = ∅, which is denoted by the empty cells in the first column.

  • Empty cell at 2nd row, 1st column denotes the situation when A = “t” and B = ∅. We would need 1 deletion to convert A to B. Here, the answer is 1.
  • Empty cell  at 3rd row, 1st column denotes the situation when A = “th” and B = ∅. We would need 2 deletions to convert A to B. Here, the answer is 2.
  • Empty cell  at 5th row, 1st column denotes the situation when A = “this” and B = ∅. We would need 4 deletions to convert A to B. Here, the answer is 4.

So, now after the trivial cases our matrix should look like this –

Edit distance matix with trivial cases

Now that you know what this matrix really means, it shouldn’t be difficult to understand that what we actually want is the value of the last empty cell, which denotes the situation when A = “this” and B = “there”.

  • Empty cell at 2nd row, 2nd column denotes the situation when A = “t” and B = “t”. The answer is 0.

Now take a moment and think, when A = “t” and B = “t”, the last characters match. Wouldn’t the answer be same as when the last characters were removed? That is, when A = ∅, B = ∅? Yes! Of course! Take another example, let A = “ste”  and B = “sto”, the edit distance currently is 1. Now, if A = “step” and B = “stop” isn’t still the edit distance 1? Yes! So, if the ending characters are same, then the edit distance is same as when these two were removed.

Looking at the matrix, if you are at the cell (i, j) can you tell which cell would be the situation when the last characters of both the strings were removed? It is the cell (i – 1, j – 1)! Moving forward,

  • Empty cell at 2nd row, 3rd column denotes the situation when A = “t” and B = “th”. The edit distance is 1.

We know that the answer is 1. But how do we derive this using the solutions we already have? Let us say the empty cell is (i, j). We can arrive at (i, j) using the result at (i – 1, j), (i – 1, j – 1) and (i, j – 1).

edit-distance-3

What does each arrow mean?

  • Insert – Cell at 2nd row 2nd column denotes A = “t” and B = “t”. So we know that the edit distance to convert “t” → “t” is 0, which is the value of the cell. Now, if we insert a character at the end, we can get “th”. So, we are doing “t” → “t” → “th”. We already know the cost of “t” → “t” and we add the cost of “t” → “th” to it. So, the value is 0 + 1.
  • Delete – Cell at 1st row 3rd column denotes ∅ → “th”. But we want “t” → “th”. If you observe, we start with A = “t” for the 2nd row. So, imagine we have A = “t∅” and we used ∅ → “th” to get “t∅” → “tth”. Now, deleting a ‘t’ would give us “tth” → “th”. It might sound really confusing, but the chain of conversions is, “t∅” → “tth” → “th”. The cost of “t∅” → “tth” is given by the cell at 1st row 3rd column and “tth” → “th” is a delete operation which costs 1. So, the value is 2 + 1.
  • Edit – Cell at 1st row 2nd column denotes the cost of ∅  → “t”. As said previously, we start with A = “t” in the 2nd row. So consider A = “t∅” and use the above conversion to get, “t∅” → “tt”. Now we apply edit operation to convert “tt” → “th”. So, the chain of operations are “t∅” → “tt” → “th”. Cost of “t∅” → “tt” is given by the value of cell at 1st row 2nd column and “tt” → “th” costs 1 edit operation. So, the value is 1 + 1.

I know the delete and edit operations sound extremely confusing, please ignore them if you don’t understand. Most tutorials just put the dynamic programming formula for the edit distance problem, write the code and be done with it. But I wanted to go one step deep and explain what that matrix meant and what each term in the dynamic programming formula (in a few moments) will mean.

So, now we had 3 options, insert, delete and update. We have calculated the total cost of choosing each option. Now which one will we choose? The one which has the least cost! If you notice in my explanation above, the cost is = 1 + value_of_respective_cell. So, now the dynamic programming formula to calculate the value of any cell is –

Edit distance formula

Where dp is the matrix. We already know the values for the first row and the first column, and the rest of the matrix can be generated using the above formula. If you notice, we are using the previous results to build the current result. This is a form of bottom-up dynamic programming.

If you fill all the cells of the matrix, it would look like –

Edit distance final matrix

The final edit distance is the last cell which is 3.

Code

If you have understood the above formula, then coding is pretty simple. You construct a 2-D array of size |A| + 1 and |B| + 1, where |A| and |B| are lengths of the strings respectively. Initialize the fist row and first column with its row and column number respectively and apply the formula above.

The code for edit distance is pretty simple. Try to code it with a clear head. It is a kind of code which people generally code without logical errors in the first go. The trick is in that formula above. If you get stuck you can use my code below as a reference.

CJava
    
    

Optimized Edit Distance Algorithm

If you have noticed, we just need the (i – 1)th row to calculate the ith row. Which means that we need not store the entire array, we could just store the previous row only. This drastically reduces the memory complexity.

Try coding using only one array of auxiliary space. You can use my code below as a reference –

CJava
    
    

Edit Distance Algorithm Complexity

The time complexity for both versions of the algorithm is O(|A| × |B|) and the memory complexity of the normal version is O(|A| × |B|) and the memory complexity of the optimized version is O(|A|) where A would be the shorter string.

Practice

Edit distance is very useful in competitive coding. You can solve these questions to get a hang of the algorithm –

I hope you have understood a little about the algorithm. The low level details of this algorithm sound very confusing, so try learning it on a high level ignoring the details if you don’t understand them yet. But do come back and take a look at my explanation! Keep practicing! Happy Coding! 😀

Binary Search Algorithm

Hello people…! In this post we will discuss one of the most commonly used search algorithm, the Binary Search. In a search algorithm, we are given an element and a collection or a set of elements. If the given element exists in the given set, we must return where it is located, or otherwise, if it does not exist, our algorithm must be able to say it does not exist.

Binary Search Conditions

The given set must obey the following rules if we want to apply binary search –

  1. All pairs of elements in the given set must be comparable. Mathematically, this is called a totally ordered set.
  2. The given set must be sorted, in ascending or descending order.

Algorithm

Let’s say we are looking for 7 in an array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Binary search compares the middle element (here 5) and the element to be searched (here 7). So, 5 is less than 7. Binary search says, “Okay so 5 is less than 7, so don’t bother about the elements left of 5 because they are less than 5 anyway. It will never be equal to 7. Continue the same job with the right half instead!”. So, now we will look at the elements right of 5 only.

Now, let’s sat the middle element is 8. This time Binary Search says, “Elements right of 8 are more than 8, they will never be equal to 7, so neglect the elements right of 8, carry on with the elements left of 8.”

So if you analyse this carefully, we are cutting the size of elements we are supposed to look at by half for each step.

To implement this algorithm, we use 3 variables –

  • low – the lowest index of the searching range.
  • high – the highest index of the searching range.
  • mid – which is calculated by the formula below

binary-search-equation-1

 

 

Let us take the previous example array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. This time let us search for 9, and this time we will find the middle element using the formula above.

binary search

Initially, low = 0 and high = 8, which gives mid = 4. The middle element is not 9, but 5 which is less than 9, so we might find 9 only to the right of 5. So, we will assign low = mid + 1.

binary search

Now, low = 5 and high = 8, which gives mid = 6. Value 7 is less than 9, so we search in the right half of 7. We do this by low = mid + 1. (If we wanted to search in the left half, say for 6 example, we would do high = mid – 1).

binary search

Even now, the middle element is less than the required element, so we must search in the right half. So we do low = mid + 1.

binary search

Now our middle element is equal to what we want, so we return this index! So basically Binary Search goes up to when there’s only one element left. If that remaining element is not the element we want, then we can claim that the given set does not contain it.

Just imagine if we were searching for 10 in the above case, we would go up to the last element and find that even the last element is not equal to 10, so we return a -1 or some value which denotes that the element is not found.

The reason the formula for calculating the middle element isn’t a simple average is to avoid an integer overflow error. If we try to calculate,

binary-search-equation-2

when low and high are close to maximum values of an integer, they can cause an integer overflow. This is why we use the formula mentioned above.

Complexity

We make one comparison per iteration. So what is the worst case? Worst case occurs when the element is not present in the given set. Then we need to iterate until we have one element left. At each iteration, we reduce the range by half, so how many iterations should we perform to reach a single element?

Binary Search complexity

It is log2 N! So the worst case complexity of binary search is O(log2 N). The best case would be if the middle element of the set is itself is the value we want to find, then, the complexity would be O(1).

Code

It is a fairly simple algorithm to code. Please try to write the code by yourself. If you get stuck, you can use my code below as a reference.

CC++JavaPython
    
    
    
    

You can code the binary search using recursion too. But I prefer the iterative version as it does not have the recursion overhead and it will not produce a stack overflow error for large arrays.

Keep practicing! Happy Coding! 🙂