Rotate matrix clockwise

Problem statement – Given an array of N rows and N columns (square matrix), rotate the matrix by 90° in clockwise direction.

Rotate matrix Theory of ProgrammingSolution – This is an implementation based problem, which means that when asked in an interview, the interviewer is mainly testing your skill to write a program which follows some set of rules. There are no tricky cases here but you might struggle in the interview if you don’t have the right approach.

For this problem, let us define a cycle like this –

Rotate matrix Theory of ProgrammingSo the cycle is a ring of elements which consists of mirroring row and column. We will solve this problem cycle-by-cycle, which means, we will rotate the 0th cycle, then the 1st cycle and so on.

Now our rotation will start from the upper left corner element. This element’s vertices (i, j) can be easily evaluated from the cycle number it is in.

Rotate matrix Theory of ProgrammingSo, if the upper left corner element of a cycle is in the cycle number c, then its position in the matrix will be (c, c). Now that we have defined one corner of our cycle, let us find the others. If n is the size of the matrix, can you find the indexes of other corners?

Rotate matrix Theory of ProgrammingOkay so n – 1 – c seems to be an important term, let us call it l (like last index).

Rotate matrix Theory of ProgrammingNow to rotate these values, we need to do –

  • int temp = arr[c][c];
  • arr[c][c] = arr[l][c];
  • arr[l][c] = arr[l][l];
  • arr[l][l] = arr[c][l];
  • arr[c][l] = temp;

Now, if we go to the next element of the ring –

Rotate matrix Theory of ProgrammingTo rotate these values, we need to do –

  • int temp = arr[c][c + 1];
  • arr[c][c + 1] = arr[l – 1][c];
  • arr[l – 1][c] = arr[l][l – 1];
  • arr[l][l – 1] = arr[l];
  • arr[c + 1][l] = temp;

Similarly, for the next item in the ring.

Rotate matrix Theory of ProgrammingWe see that the indices vary by 0, 1, 2, etc. This can be generalized into a loop variable, say i

Rotate matrix Theory of ProgrammingSo, for any matrix, number of cycles c will be from [0, … n / 2]. If you think about it even number sized matrices have n / 2 cycles. Odd number sized matrices have n / 2 + 1 cycles, but the inner-most cycle would be a single integer which doesn’t need to be touched.

Value of i will be from [0 … , l – c). Why? Because we need to increment i, until c + i < l. So i < l – c.

So you have two loops and inside them, we need to write those 5 statements which make the rotation. Simple isn’t it? Try to code it, you can refer to my code below if you get stuck.

Code

public static void rotate(int[][] arr) {
    int n = arr.length;

    for (int c = 0; c < n / 2; ++c) {
        int l = n - 1 - c;

        for (int i = 0; i < l - c; ++i) {
            int temp = arr;

            arr = arr[l - i];
            arr[l - i] = arr[l][l - i];
            arr[l][l - i] = arr[l];
            arr[l] = temp;
        }
    }
}

Keep practicing! Happy Coding! 😀

Print matrix in spiral order

Problem statement – Given a 2D array (or matrix) of N rows and M columns, print it in a spiral order. Example, for the below matrix –

int[] arr = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9},
            };

The output is –

1 2 3 6 9 8 7 4 5

Solution – When an interviewer asks you this question, he/she is just testing your implementation skills. This question isn’t tough because it doesn’t have any corner cases, but it is quite tough to solve if you start over thinking.

Let us label the rows/columns which we must print –

Print matrix in spiral order Theory of ProgrammingSo, our top-most row is top, bottom-most row is bottom, left-most column is left and right-most column is right. As we keep printing elements of the matrix, we will bring them closer to each other. Initially –

  • top = 0
  • right = M – 1
  • bottom  = N – 1
  • left = 0

As per the arrow indication, in our top row, we will print elements from left to right. So the loop to print it will look something like –

for (int i = left; i <= right; ++i) {
    print arr[top][i];
}

++top;

As you have noticed, the ++top is to bring it towards the center. Similarly, for printing the right column –

for (int i = top; i <= bottom; ++i) {
    print arr[i][right];
}

--right;

Similarly, for printing the bottom row –

for (int i = right; i >= left; --i) {
    print arr[bottom][i];
}

--bottom;

Similarly, for printing the left column –

for (int i = bottom; i >= top; --i) {
    print arr[i][left];
}

++left;

Now all that’s left is to execute this printing in a proper order. We could have a control variable dir, which denotes the direction. If –

  • dir == 1, print top row
  • dir == 2, print right column
  • dir == 3, print bottom row
  • dir == 4, print left column

We must keep rotating the value of dir between 1, 2, 3, 4 as long as top ≤ bottom and left ≤ right. If you have understood the logic, you should be able to write the code easily. If you didn’t just go through the explanation once more, it is can be tricky 😛

Code

public static void printInSpiralOrder(final int[][] arr) {
    if (arr.length == 0 || arr[0].length == 0) {
        return;
    }

    int top = 0, bottom = arr.length - 1, left = 0, right = arr[0].length - 1;
    int dir = 1;

    while (top <= bottom && left <= right) {
        if (dir == 1) {    // left-right
            for (int i = left; i <= right; ++i) {
                System.out.print(arr[top][i] + " ");
            }

            ++top;
            dir = 2;
        } else if (dir == 2) {     // top-bottom
            for (int i = top; i <= bottom; ++i) {
                System.out.print(arr[i][right] + " ");
            }

            --right;
            dir = 3;
        } else if (dir == 3) {     // right-left
            for (int i = right; i >= left; --i) {
                System.out.print(arr[bottom][i] + " ");
            }

            --bottom;
            dir = 4;
        } else if (dir == 4) {     // bottom-up
            for (int i = bottom; i >= top; --i) {
                System.out.print(arr[i][left] + " ");
            }

            ++left;
            dir = 1;
        }
    }
}

Keep practicing! Happy Coding! 😀

Add one to digit array

Problem statement – Given a non-negative integer in the form of an array of digits, add one to digit array. The digits are stored such that the most significant digit is at the head of the list. Eg. –

    A = {1, 3, 5}, answer = {1, 3, 6}

Solution – When an interviewer asks questions like these, he is testing your implementation skills and you ability to discover the corner cases. The solution is simply to add 1 to the last digit and pass on the carry until the first digit. But there are a few cases to handle, like –

  • A = {2, 4, 9}, answer = {2, 5, 0}
  • A = {9, 9}, answer = {1, 0, 0}
  • A = {0, 0, 1, 9}, answer = {2, 0}
  • A = {0}, answer = {1}

If we have passed the carry value to the end of the array and we still have carry left, then that would be appended as the new most significant bit. The digit array may be having leading zeroes, you should trim them before proceeding to solve the problem. But don’t blindly trim all leading zeroes, you should also handle the case when we have just a 0.

This is a simple problem to code, if you are aware of all the corner cases. Try it on your own once. 🙂

Code

public ArrayList<Integer> plusOne(ArrayList<Integer> arr) {
    preprocessInput(arr);
    
    int carry = 1;
    
    for (int i = arr.size() - 1; i >= 0; --i) {
        if (carry == 0) {
            return arr;
        }
        
        int num = arr.get(i);
        
        num++;
        
        arr.set(i, num % 10);
        carry = num / 10;
    }
    
    if (carry == 1) {
        arr.add(0, carry);
    }
    
    return arr;
}

public void preprocessInput(ArrayList<Integer> arr) {
    while (arr.size() > 1) {
        if (arr.get(0) == 0) {
            arr.remove(0);
        } else {
            break;
        }
    }
}

Keep practicing! Happy Coding! 😀

First missing integer in an unsorted array

Problem statement – Given an unsorted integer array, find the first missing positive integer. Example,

  • If A = [-1, 4, 2, 3, 5], missing integer = 1.
  • If A = [1, 5, 2, 3, 4, 7], missing integer = 6.
  • If A = [-1, -2, -3, -4], missing integer = 1.

Clues

  • Your solution should be O(N) in time and O(1) in space.
  • Can you make changes in the array such that you can mark which numbers in 1 to N are already present in the array?

Solution – This is a little difficult one, so pay attention! If you go through the problem statement carefully, your solution will be an integer between 1 to N + 1, where N is the size of the array. Why N + 1? If the array had all integers from 1 to N, then the missing integer would be N + 1!

Now that we know our solution will be an integer from 1 to N + 1, we need to come up with a mechanism to mark/flag the numbers in 1 to N + 1, which are already present in the array. If we could use O(N) space, then we could create a boolean array isPresent[] of size N + 1, and set isPresent[A[i]] = true. The solution would be something like this –

boolean[] isPresent = new boolean[N + 1];

for (int i = 0; i < A.length; ++i) {
    isPresent[A[i]] = true;
}

for (int i = 1; i < isPresent.length; ++i) {
    if (!isPresent[i]) {
        return i;
    }
}

return N + 1;

But since our solution should be O(1) in space, we need to do this marking in our input array itself. Can we take advantage of the fact that the indices of an array is a contiguous span of numbers from 1 to N? Yes!

We will do this by making numbers at certain indexes negative. The idea is that, let’s say, we have A[i] = 3, then we will make A[3] negative. So that, when we make another scan of the array A, and we see A[3] is negative, we know that 3 has occurred somewhere in the array. Read the previous sentence once more, let it sink in. Now let’s write it as a formula –

int value = A[i];
A[value] = -A[value];

Now the question is, what if A[i] is negative? Let’s handle that case in our newly born formula.

int value = Math.abs(A[i]);
A[value] = -A[value];

Now the question is, what if A[value] is already negative? Let’s handle that case in our formula –

int value = Math.abs(A[i]);
A[value] = -Math.abs(A[value]);

So we will apply this formula to all the elements in the array by iterating over the whole array. Now, we will make another iteration over the array. If at any index i, we get A[i] as positive, then it means that the integer i was not present in the input array, otherwise A[i] would have been negative! So integer i is our missing integer. Read the solution again if you didn’t understand it in the first reading (I didn’t either 😛 )

Before you race off to code, there are a couple of issues we must handle. Firstly, what if we have negative integers or integers greater than N in our array? We know that our solution will be an integer between 1 and N + 1, so any other integer is junk for us. So we can replace all of them with a constant, say a variable called FLAG. So, when we encounter them in our formula loop, we can ignore them. Now keep in mind that they might have become negative because of some other element in the array. So, in our formula loop, we must ignore elements with values FLAG and -FLAG.

Secondly, up until now, for the sake of simplicity we spoke in terms of 1 indexed arrays, but we know that in real code, we have 0 indexed arrays. I guess you can handle that 😉

Code

public class Solution {
	public int firstMissingPositive(ArrayList<Integer> a) {
	    final int N = a.size();     // size
	    // a dummy value to replace
	    // integers below 0 and above N
	    final int FLAG = N + 2; 
	    
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) <= 0 || a.get(i) > N) {
	            a.set(i, FLAG);
	        }
	    }
	    
	    // Our formula loop
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) == FLAG || a.get(i) == -FLAG) {
	            continue;
	        }
	        
	        int value = Math.abs(a.get(i));
	            
	        a.set(value - 1, -Math.abs(a.get(value - 1)));
	    }
	    
	    // Loop through collection. Whichever
	    // index holds a +ve integer is the answer
	    for (int i = 0; i < N; ++i) { if (a.get(i) > 0) {
	            return i + 1;
	        }
	    }
	    
	    // If the collection has all integers
	    // from 1 to N, then answer is N + 1
	    return N + 1;
	}
}

Maximum sum contiguous sub-array

Problem statement – Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array A[0, 1, 2 … N], we need to find a sub-array A[i, i + 1, i + 2, … j] such that the sum of elements in the sub-array is maximum.

Clues

  • Your solution should be O(N) in time and O(1) in space.
  • Can you think of a solution which solves the problem in a single scan of the array?

Solution – This is a popular interview question asked by the interviewers to test the basics of the candidate. This problem can be solved in O(N) time by using Kadane’s Algorithm. In this algorithm, we keep adding elements to a sum variable as we are traversing the array. This sum variable holds the sum of a sub-array. When the sum variable becomes negative, we cast off the the sub-array seen so far and reset sum variable. The final answer will be the maximum of all the values which were stored in sum over all iterations.

Example – For the array A = [-2 , 1, -3, 4, -1, 2, 1, -5, 4]

A[i] Sub-array sum Max sub-array maxSum
-2 [-2] 0 [-2] -2
1 [1] 1 [1] 1
-3 [-3] 0 [1] 1
4 [4] 4 [4] 4
-1 [4, -1] 3 [4] 4
2 [4, -1, 2] 5 [4, -1, 2] 5
1 [4, -1, 2, 1] 6 [4, -1, 2, 1] 6
-5 [-5] 3 [4, -1, 2, 1] 6
4 [-5, 4] 3 [4, -1, 2, 1] 6

Code

public class Solution {
	public int maxSubArray(List<Integer> a) {
	    int sum = 0;
	    int maxSum = Integer.MIN_VALUE;
	    
	    for (int i = 0; i < a.size(); ++i) {
	        if (sum + a.get(i) < 0) {
	            // Adding this element will make the current
	            // subarray sum negative, so don't add this element
	            // and start a new subarray with next element
	            sum = 0;
	        } else {
	            // Adding this element will increase the
	            // current subarray sum, so add this
	            // element to the current subarray
	            sum += a.get(i);
	        }
	        
	        // maxSum is the maximum of -
	        //
	        // 1. maxSum so far
	        // 2. if sum == 0, then a.get(i) which is proably a -ve number
	        // 3. if sum != 0, then sum of subarray so far
	        maxSum = Math.max(maxSum, sum == 0 ? a.get(i) : sum);
	    }
	    
	    return maxSum;
	}
}

If you didn’t understand why we need the “sum == 0 ? a.get(i) : sum” condition in the end, think of the case where array A = [-3, -2, -1]. Basically when the array has all negative values, you’d want to return the largest among the negative values. Now remember, sum variable doesn’t store negative values, so when it holds 0, we consider A[i] instead of sum. Give it a little thought, I’m sure you’ll understand it. If you need a more explanation, refer to my post on Kadane’s Algorithm.

Find the majority element in an array

Problem statement – Given an unsorted array, find the majority element (element which occurs for more than N/2 times).
Clues

  • Solution must be O(N) in time and O(1) in space.
  • If the majority element exists, there will only be one such element. How can we find it?

Solution – We can do this in O(N) time by the Boyer–Moore majority voting algorithm. It is a simple 3-step algorithm –

  • Initialization – We will take 2 variables, ‘candidate’ and ‘votes’ and set them to 0.
  • Voting – Traverse through the array once. If votes is 0, then we set candidate to the current element. We will also check, if the current element (arr[i]) is equal to the candidate, if yes, increment votes, else decrement.
  • Checking the winning candidate – After Step 2, we will compute the frequency of the value in candidate. If this is more than N/2, then the candidate is the majority element, otherwise, the majority element does not exist.

So this is kind of like picking a candidate and computing how many votes he has. You may not understand it in the first glance, but try reading the logic two more times and try to write the pseudo-code for this. Believe me, this is a ridiculously simple algorithm!

Code

// Moore's Majority Voting Algorithm procedure
// Computes the majority element in O(N) time
// Returns the majority element
// If no majority element, returns INT_MIN
int majorityElement(int arr[], int length)
{
    int votes = 0, candidate = -1, i;
     
        // Voting
    for (i = 0; i < length; ++i) {
        if (votes == 0) {
            candidate = arr[i];
        }
         
        if (candidate == arr[i]) {
            ++votes;
        } else {
            --votes;
        }
    }
     
    votes = 0;
     
    // Get freq. of candidate
    for (i = 0; i < length; ++i) { if (arr[i] == candidate) { ++votes; } } // Verify if the candidate // is the majority element if (votes > length / 2) {
        return candidate;
    } else {
        return INT_MIN;
    }
}

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).

Code

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;
}