Find Local Minimum in an unsorted array with unique elements

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-local-minima-in-a-given-array/.

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1].

Examples:

a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

Solution:

Brute force 
Go through each element 3 tuples, and compare them.
Time complexity - O(n)

Solution 2
Can we do better? The answer is yes, we can do this in O(log n). Lets see how.

mid=(start+end)/2; 
1. If there is just one array element, it's a local minimum.
2. If there are two array elements, check each. One must be a local minimum.
3. Otherwise, look at the middle element of the array. 
   If it's a local minimum, return it. 
   Otherwise, at least one adjacent value must be smaller than this one. 
   Recurse in the half of the array containing that smaller element 
   (but not the middle).

Here is the code in java:

public class LocalMinimum {

 public static int findLocalMinimum(int[] elements, int lowIndex, int highIndex) {
  if (lowIndex > highIndex) {
   return -1;
  }

  if (lowIndex == highIndex) {
   return lowIndex;
  }

  if (lowIndex + 1 == highIndex) {
   if (elements[lowIndex] < elements[highIndex]) {
    return lowIndex;
   }
   return highIndex;
  }

  int midIndex = (lowIndex + highIndex) / 2;

  if ((elements[midIndex] <= elements[midIndex - 1])
    && (elements[midIndex] <= elements[midIndex + 1])) {
   return midIndex;
  }

  if (elements[midIndex] >= elements[midIndex + 1]) {
   return findLocalMinimum(elements, midIndex, highIndex);
  } else {
   return findLocalMinimum(elements, lowIndex, midIndex);
  }
 }
 
 public static void main(String[] args){
  int Arr[] = {8,5,4,3,1,2,6,9};
  int index = findLocalMinimum(Arr, 0, Arr.length-1);
  System.out.println("local mimimum is "+Arr[index]);
 }

}

Time complexity

T(1) ≤ 1
T(2) ≤ 1
T(n) ≤ T(n / 2) + 1

Using the Master Theorem, you can show that this algorithm runs in time O(log n), as required.

[Edit] - Note

1. We are not enumerating all the local minima in the array, but a single LM, which can be done in O(log n) time.
   The number of local minima can be n/2; you can't enumerate them all in O(log n) time.
   
2. It also doesn't guarantee whether we will get global minima or not. Consider the array
   {8,5,4,3,1,2,6,9}, the output will be 1, as it is only LM here, not because it is a global minima.
3. The method doesn't guarantee any particular local minima. Consider the array : {8,5,4,3,6,4,5,1,2,6,4,5,9}. The LM outputted by the code will be 3, which is one of the LMs in the array. The LMs we had in array were 3,4,1,4. But the code returned 3, which is one of the LMs. 

Reference
http://stackoverflow.com/questions/12238241/find-local-minima-in-an-array

Thanks

Read More

Sorted Linked List to Balanced BST

Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.

Example : 

Input: Linked List 1->2->3->4->5->6->7
Output: A Balanced BST
        4
      /   \
     2     6
   /  \   / \
  1   3  4   7  

Lets discuss 2 approaches for this problem.

Solution
Method 1 (Simple)
Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed.

1) Get the Middle of the linked list and make it root.
2) Recursively do same for left half and right half.
       a) Get the middle of left half and make it left child of the root
          created in step 1.
       b) Get the middle of right half and make it right child of the
          root created in step 1.

Time complexity: O(nLogn) where n is the number of nodes in Linked List.This is because each level of recursive call requires a total of n/2 traversal steps in the list, and there are total log(n) number of levels.

Method 2 (Tricky)
The method 1 constructs the tree from root to leave, i.e. top down approach.

Now lets follow bottom up approach. In this method, we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.

public TreeNode sortedListToBST(ListNode head,int start, int end) {
 if(start>end) return NULL;
 int mid = (start+end)/2;
 TreeNode leftChild = sortedListToBST(list, start, mid-1);
 TreeNode parent = new TreeNode();
 if(parent==null)
  System.out.println("Memory error");
 parent.setData(list.getData());
 parent.setLeft(leftChild);
 list = list.getNext();
 parent.sertRight(sortedListToBST(list,mid+1,end));
 return parent;
}
//method caller
sortedListToBST(head,0,n-1);

While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
Time complexity = O(n)

Read More

Convert sorted array to Balanced BST

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/convert-sorted-array-to-height-balanced-binary-search-tree/.

Problem 

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Examples

Input: 1 2 3 4 5 6 7

Output:

    4
   / \
  3   6
 / \ / \
3  4 6  7

Solutions

 Method 1 - Take the array's middle element and insert it recursively

• Pick up the middle element of the array
• Set it as the root
• Recursively build up left and right subtrees with lower and higher halves of the array

Here is the code in java:

public static BST sortedArrayToBST(int[] arr){
    Node bst = new Node();
    bst = sortedArrayToBST(arr, 0, arr.length-1, bst);
    return bt;
}

private static Node sortedArrayToBST(int[] arr, int start, int end) {

    if( start == end){
        bst.insert(new Node(arr[start]));
        return;
    }
    else if(start > end) {
        return;
    }
    int middle = (start+end)/2;
    Node node = new Node(arr[middle]);
    //bst.insert(new Node(arr[middle]));
    node.left = sortedArrayToBST(arr, start, middle - 1);
    node.right = sortedArrayToBST(arr, middle+1, end);
    return node;
}

Time complexity - O(n)
Space Complexity - O(1) (but if you internally think of recursion, it will be kind of O(n)

Read More

Implement a stack using 2 queues

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-stack-using-queues/.

Problem : Implement a stack using 2 queues and standard operations (enqueue, dequeue, isempty, size)

Solution
 
A similar problem has been blogged here, where we implement a queue using 2 stacks.

There should be TWO versions of the solution.

• Version A: The stack should be efficient when pushing an item.
• Version B: The stack should be efficient when popping an item.

Method 1 - When push is efficient and pop is costly
In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.

push() : 
     enqueue in queue1
pop() :
     while (size of queue1 is bigger than 1)
           pipe de-queued items from queue1 into queue2
     de-queue and return the last item of queue1, 
     then switch the names of queue1 and queue2

Method 2 - When pop is efficient, but push is costly

push():
   enqueue in queue2
   enqueue all items of queue1 in queue2, 
        then switch the names of queue1 and queue2
pop():
   deqeue from queue1

Example of Method 1

Lets say we want to insert 1,2,3.
Step 0:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Step 1:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 | 2 | 3 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Step 2:While popping

"Stack"
+---+---+---+---+---+
| 3 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 | 2 |   |   |   |  | 3 |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Step 3:

"Stack"
+---+---+---+---+---+
| 3 | 2 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  | 3 | 2 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

and so on. Finally we take out 1, and put it in B.

Example of Method 2
Lets say we want to insert 1,2,3.
Step 0:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Step 1:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Step 2:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  | 2 | 1 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Step 3:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Reference - stackoverflow.
Thanks.

Read More

Stack with find-min/find-max in O(1) time

Problem

Stack with find-min/find-max in O(1) time

Solution

Method 1 - using extra stacks for min and max
The basic idea of the solution can be found here.

Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element.
Now the operations will be following  :
push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'. Similarly for max_stacks

pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2 8

original_stack                min_stack                   max_stack
        8                                 1                       8

        2                                 1                       7

        1                                 1                       7

        9                                 3                       7

        8                                 3                       7

        5                                 3                       7

        3                                 3                       7

        7                                 7                       7

Now the pop will result in popping of 8 from original stack, 1 from min stack and 8 from max stack. Now if you try to get minimum, you have to just say min_stack.peek() or for max max_stack.peek().

But currently we are using 3 stacks, but can we do better?

Method 2 - Optimizing method 1
Although the above method is right, but we can still do better. If the stack has lot of elements, then we are wasting a lot of space. However, we can save this useless space as follow:

Instead of saving min(or max) value with each element, we can use two stacks. Because change in the minimum(or maximum) value will not be so frequent, we push the min(or max) value to its respective stack only when the new value is <=(or >=) to the current min(or max) value.

public class StackWithMinMax extends Stack<Integer> {

    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax () {
        minStack = new Stack<Integer>();    
        maxStack = new Stack<Integer>();    
    }

    public void push(int value){
        if (value <= min()) { // Note the '=' sign here
            minStack.push(value);
        }

        if (value >= max()) {
            maxStack.push(value);
        }

        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();         
        }

        if (value == max()) {
            maxStack.pop();         
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public int max() {
        if (maxStack.isEmpty()) {
            return Integer.MIN_VALUE;
        } else {
            return maxStack.peek();
        }
    }
}

Example

Stack : MinStack : MaxStack

7         7         7
4         4         7
5         1         8 (TOP)
6         1 (TOP)         
7
8                 
1                  
1                  
7
2
4
2 (TOP)     

Thanks
Reference - stackoverflow

Read More

Algorithm Introduction

Definition: 

An algorithm is a finite set of discrete statements (or Steps) in some particular sequence (or Order) to accomplish a predefined particular task.

Properties:  

An algorithm must have the following properties:

Input(s)      : An algorithm must have one(1) or more pre-specified input(s).

Output(s)     : An algorithm must have one(1) or more output(s).

Definiteness  : Each steps of an algorithm must define clearly (i.e. without any confusion or Contradiction or Ambiguity).

Finiteness    : Each steps of an algorithm must be terminated in finite(tolerable) amount of time.

Effectiveness : Any calculations performed / Decision taken by a computer or any electronic machine with respect to an algorithm should be computable by the human beings with pencil and paper although time may be longer.

Correctness   : An algorithm should always produce correct result with respect to it's domain ( of the inputs ).

Classification of Algorithms in terms of Flow of Control: 

Algorithm can be classified two category as follows:

• Iterative Algorithm: In this category of algorithm mainly Loop are used to solve a difficult problem in simple manner.
  

• Recursive Algorithm: In this category of algorithm the concept of Recursion are used to solve a difficult problem in simple manner.    
  

What is Loop?

Loop is a concept where a set of statement(s) written in a block with in the algorithm will be computed a finite number of times, limited by some condition(s).

Example of an iterative algorithm:

Sample-algorithm(N, s)
1. i = 0, s = 0.
2. WHILE ( i <= N)        [ Start of Loop ]
      s = s + i.
      i = i + 1 
   EndWhile               [ End of Loop ]
3. Return



What is Recursion?
In recursion, in contrast with loop, has the following properties:

• An algorithm should be capable to Call Itself.

• There should be some Base Criteria, for which the algorithm should not call itself.

• Each time the algorithm will call itself, result should converge toward the solution of the problem.

Example of an recursive algorithm:

Sample-algorithm(N, s)
1. i = 0, s = 0.
2. Call Rec-Add(N, s, i)
3. Return

Rec-Add(N, s, i)
1. IF (i > N ) Return.           [ Base Criteria, No More Call ]
2. s = s + i.
3. Call Rec-Add(N, s, (i+1))     [ Calling itself ]
4. Return.

Here Rec-Add is defined recursively not iteratively. 

Reference - here

Read More

Find the minimum and maximum in the array

Here are few question we find on finding min and max in the array, but array type changes.

Unsorted 1D array

• Find the maximum (OR minimum) in an array
• Find the maximum AND minimum in an array with min number of comparisons
• Find the max and second maximum in an array (likewise for minimum)
• Find the max and nth max in an array

Rotated Sorted array

• Find the minimum element in the rotated sorted array.
• Find Nth largest element in the rotated sorted array

Read More

Find Maximum Value in the unsorted array

Problem : 
Find Maximum Value in the unsorted array

Solution
Method 1 - Linear search

Here is the code to do that :

public int findMax(int[] numbers)
{
    int max = 0;

    for (int i = 0; i < numbers.length; ++i)
        if (numbers[i] > max) max = numbers[i];

    return max;
}

So, in worst case the number of comparisons will be (n-1).

Time complexity - O(n)

Read More

Find kth largest in an Array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/kth-largest-element-in-an-array/.

Problem : 

 You have an array of numbers; you need to find the k-th largest in the arra

 Solution

Method 1 - Tournament principle
We have to find the element which has competed with largest element, and is just (k-1)th level.We have discussed this principle here.

Method 2 - Using max heap

Consider the array of length n. Here is the algo : 

• Build a max heap in O(n) ; 
• Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn) 
• To understand building MAX heap in O(n) check heap.

Method 3 - Modified bubble sort running k times
1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(nk)
Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 4 - Use temporary array
K largest elements from arr[0..n-1]
1) Store the first k elements in a temporary array temp[0..k-1].
2) Find the smallest element in temp[], let the smallest element be min.
3) For each element x in arr[k] to arr[n-1]
If x is greater than the min then remove min from temp[] and insert x.
4) Print final k elements of temp[]
Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)

Method 5 - Use Min Heap
This method is mainly an optimization of method 4. Instead of using temp[] array, use Min Heap.
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
       a) If the element is greater than the root then make it root and call heapify for MH
       b) Else ignore it.
// The step 2 is O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.
Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)
All of the above methods can also be used to find the kth largest (or smallest) element.


Method 6 - Use Sorting
1) Sort the elements in descending order in O(nLogn)
2) Print the first k numbers of the sorted array O(k).
Time complexity: O(nlogn)

Method 7 - Use Order Statistics
If you want a true O(n) algorithm, as opposed to O(kn) or something like that, then you should use quickselect (it's basically quicksort where you throw out the partition that you're not interested in). This is called finding the k-th order statistics.

There's a very simple randomized algorithm (called quickselect) taking O(n) average time, and a pretty complicated non-randomized algorithm taking O(n) worst case time. There's some info on Wikipedia, but it's not very good.
Everything you need is in these powerpoint slides. Also, refer quicksort and randomized selection to find introductory help on randomized algorithm.


Just to extract the basic algorithm of the O(n) worst-case algorithm:

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

The algorithm is discussed in detail here.

Method 8 - Compare 3 elements if N=3 (like wise for N)

int third_biggest(int *arr, int size)
{
 int first = INT_MIN, second = INT_MIN, third = INT_MIN;
 for(int i=0;i first)
  {
   third = second;
   second = first;
   first = arr[i];
  }
  else if(arr[i] > second)
  {
   third = second;
   second = arr[i];
  }
  else if(arr[i] > third)
  {
   third = arr[i];
  }
 }
 return third;
}

Ofcourse, method 7 is best :)

Read More

find out the largest and second largest number in an array

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-second-largest-element-in-an-array/.

Question: Write an efficient C program to find smallest and second smallest element in an array.

Solution
Method 1 - Compare each element with current max and second max

Algorithm

1) Initialize both first and second smallest as a[0]
   first = second = a[0]
2) Loop through all the elements.
   a) If the current element is greater than firstMax, then update firstMax 
       and secondMax. 
   b) Else if the current element is greater than second then update 
    secondMax

pseudocode

largest = numbers[0];
secondLargest = null
for (i=1 to numbers.length-1) {    
    if numbers[i] > largest {
        secondLargest = largest;
        largest = numbers[i];
    else
        if numbers[i] > secondLargest {
            secondLargest = numbers[i];
        }
    }
}

Time Complexity: O(n)
 Number of comparisons atmost will be 2(N-1)

Method 2 - Tournament principle

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.
First, compare the elements, as in the tree

   |
  / \
 |   |
/ \ / \
x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.
The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.

Example-

1. Start with comparing elements of the n element array in odd and even positions and determining largest element of each pair. This step requires n/2 comparisons. Now you've got only n/2 elements. Continue pairwise comparisons to get n/4, n/8, ... elements. Stop when the largest element is found. This step requires a total of n/2 + n/4 + n/8 + ... + 1 = n-1 comparisons.
2. During previous step, the largest element was immediately compared with log₂(n) other elements. You can determine the largest of these elements in log₂(n)-1 comparisons. That would be the second-largest number in the array.

 So, looking at the tree above, 9 is the winner, but we find 2nd winner on level 2 and so on.

From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20  

Here is the code for tournament principle:

Here is the solution taken from stackoverflow:
To make things work, there are two assumptions:
1) number of elements in the array is the power of 2
2) there are no duplicates in the array
The whole process consists of two steps:
1. building a 2D array by comparing two by two elements. First row in the 2D array is gonna be the entire input array. Next row contains results of the comparisons of the previous row. We continue comparisons on the newly built array and keep building the 2D array until an array of only one element (the largest one) is reached.
2. we have a 2D-array where last row contains only one element: the largest one. We continue going from the bottom to the top, in each array finding the element that was "beaten" by the largest and comparing it to the current "second largest" value. To find the element beaten by the largest, and to avoid O(n) comparisons, we must store the index of the largest element in the previous row. That way we can easily check the adjacent elements. At any level (above root level),the adjacent elements are obtained as:

leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,

where rootIndex is index of the largest(root) element at the previous level.

public static Integer findSecondLargest(List<Integer> list) {
        if (list == null) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        List<List<Integer>> structure = buildUpStructure(list);
        System.out.println(structure);
        return secondLargest(structure);

    }

    public static List<List<Integer>> buildUpStructure(List<Integer> list) {
        List<List<Integer>> newList = new ArrayList<List<Integer>>();
        List<Integer> tmpList = new ArrayList<Integer>(list);
        newList.add(tmpList);
        int n = list.size();
        while (n>1) {
            tmpList = new ArrayList<Integer>();
            for (int i = 0; i<n; i=i+2) {
                Integer i1 = list.get(i);
                Integer i2 = list.get(i+1);
                tmpList.add(Math.max(i1, i2));
            }
            n/= 2;
            newList.add(tmpList);   
            list = tmpList;
        }
        return newList;
    }

    public static Integer secondLargest(List<List<Integer>> structure) {
        int n = structure.size();
        int rootIndex = 0;
        Integer largest = structure.get(n-1).get(rootIndex);
        List<Integer> tmpList = structure.get(n-2);
        Integer secondLargest = Integer.MIN_VALUE;
        Integer leftAdjacent = -1;
        Integer rightAdjacent = -1;
        for (int i = n-2; i>=0; i--) {
            rootIndex*=2;
            tmpList = structure.get(i);
            leftAdjacent = tmpList.get(rootIndex);
            rightAdjacent = tmpList.get(rootIndex+1); 
            if (leftAdjacent.equals(largest)) {
                if (rightAdjacent > secondLargest) {
                    secondLargest = rightAdjacent;
                }
            }
            if (rightAdjacent.equals(largest)) {
                if (leftAdjacent > secondLargest) {
                    secondLargest = leftAdjacent;
                }
                rootIndex=rootIndex+1;
            }
        }

        return secondLargest;
    }

Reference - stackoverflow

Read More

How to find max. and min. in array using minimum comparisons?

Problem : Given an array of integers find the max. and min. using minimum comparisons.

Solution
Method 1 (Naive) - Iterate through the array, and update min and max pointers

1. Iterate through the array, select element a
2. Update min by comparing (min, a)
3. Update max by comparing (max, a)

Number of comparison here will be ~2N, if N is number of element.
Time complexity will be O(n) though.

Method 2 - Pick 2 elements at time, compare them and compare them with corresponding min and max

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.(Actually it is 3N/2 if N is even, and 3(N-1)/2 if N is odd)

Example
Consider

A = [a1, a2, a3, a4, a5]

Compare a1 & a2 and calculate min12, max12:

if (a1 > a2)
  min12 = a2
  max12 = a1
else
  min12 = a1
  max12 = a2

Similarly calculate min34, max34. Since a5 is alone, keep it as it is...

This way you would do 3 comparisons for 2 elements, amounting to 3N/2 total comparisons for N elements.


Iterative solution

class Pair 
{
   public int min;
   public int max;
}
public Pair getMinMax(int arr[], int n)
{
  Pair minmax;    
  int i; 
 
  // If array has even number of elements then
  //  initialize the first two elements as minimum and
  //  maximum 
  if (n%2 == 0)
  {        
    if (arr[0] > arr[1])    
    {
      minmax.max = arr[0];
      minmax.min = arr[1];
    } 
    else
    {
      minmax.min = arr[0];
      minmax.max = arr[1];
    }
    i = 2;  // set the startung index for loop 
  } 
 
   // If array has odd number of elements then
   // initialize the first element as minimum and
   // maximum 
  else
  {
    minmax.min = arr[0];
    minmax.max = arr[0];
    i = 1;  // set the startung index for loop 
  }
   
  // In the while loop, pick elements in pair and
  //   compare the pair with max and min so far    
  while (i < n-1) 
  {         
    if (arr[i] > arr[i+1])         
    {
      if(arr[i] > minmax.max)       
        minmax.max = arr[i];
      if(arr[i+1] < minmax.min)         
        minmax.min = arr[i+1];       
    }
    else        
    {
      if (arr[i+1] > minmax.max)       
        minmax.max = arr[i+1];
      if (arr[i] < minmax.min)         
        minmax.min = arr[i];       
    }       
    i += 2; //Increment the index by 2 as two
            //   elements are processed in loop 
  }           
 
  return minmax;
}    

Method 3 - Tournament Method
This is similar to previous method, where we were taking 2 elements at a time. Here we are doing this in local subarray recursively and returning elements accordingly.

Pair MaxMin(array, array_size)
   if array_size = 1
      return element as both max and min
   else if arry_size = 2
      one comparison to determine max and min
      return that pair
   else    // array_size  > 2 
      recur for max and min of left half
      recur for max and min of right half
      one comparison determines true max of the two candidates
      one comparison determines true min of the two candidates
      return the pair of max and min

Here is the code

void minmax (int[] a, int left, int right, int min, int max) {
  int lmin, lmax, rmin, rmax, mid;
  if (left==right) {
    min = a[left];
    max = a[right];
  } else if (right == left+ 1) {
    if (a[left] > a[right]) {
      min = a[right];
      max = a[left];
    } else {
      min = a[left];
      max = a[right];
    }
  } else {
    mid = (left+right) / 2;
    minmax(a,left, mid, lmin, lmax);
    minmax(a, mid + 1,right, rmin, rmax);
    min = (lmin > rmin) ? rmin : lmin;
    max = (lmax > rmax) ? lmax : rmax;
  }
}

Thanks.

References -stackoverflow , geeksforgeeks

Read More

Determine if a small tree T2 is the subtree of a huge tree T1

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/subtree-of-another-tree-problem/.

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Solution
Method 1 - Traversing through T1 and finding subtree at each node, if T1's node = T2.root
Here's what we will do:

• Traverse T1. 
• If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time. 
• Compare the current node. If they are always equal, T2 is a subtree of T1.

public static boolean isSubtree(BinaryTreeNode<Integer> T1,
        BinaryTreeNode<Integer> T2) {
    if (T1 == null)
        return false;
    else if (T1.data.equals(T2.data) && isTwoTreeEqual(T1, T2)) {
        return true;
    } else {
        return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
    }
}
 
public static boolean isTwoTreeEqual(BinaryTreeNode<Integer> root1,
        BinaryTreeNode<Integer> root2) {
    if (root1 == null && root2 == null)
        return true;
    else if (root1.isLeaf() && root2.isLeaf())
        return root1.data.equals(root2.data);
    else if (!root1.isLeaf() && !root2.isLeaf()) {
        if (!root1.data.equals(root2.data))
            return false;
        return isTwoTreeEqual(root1.left, root2.left)
                && isTwoTreeEqual(root1.right, root2.right);
    } else
        return false;
}

Though this is good, but we may run out of memory stack, as we are recursing in 2 functions, and isTwoTreeEqual can be improved.

public static boolean containsTree(BinaryTreeNode<Integer> T1,
        BinaryTreeNode<Integer> T2) {
    if (T2 == null)
        return true; // The empty tree is always a subtree
    else
        return subTree(T1, T2);
}
 
private static boolean subTree(BinaryTreeNode<Integer> r1,
        BinaryTreeNode<Integer> r2) {
    if (r1 == null)
        return false; // big tree empty & subtree still not found.
    if (r1.data == r2.data) {
        if (matchTree(r1, r2))
            return true;
    }
    return (subTree(r1.left, r2) || subTree(r1.right, r2));
}
 
private static boolean matchTree(BinaryTreeNode<Integer> r1,
        BinaryTreeNode<Integer> r2) {
    if (r2 == null && r1 == null)
        return true; // nothing left in the subtree
    if (r1 == null || r2 == null)
        return false; // big tree empty & subtree still not found
    if (r1.data != r2.data)
        return false; // data doesn’t match
    return (matchTree(r1.left, r2.left) && matchTree(
            r1.right, r2.right));
}

Time complexity -O(n+m), where n is size of T1, and m of T2
If k is the number of occurrences of T2’s root in T1, the worst case runtime can be characterized as O(n + k * m).

Method 2 -Pre process the tree T1

1. Pre-process the T1 tree, keeping the list of all possible subtree roots (the cache list will have a millions of entries)
2. Sort the cached list of roots by the descending order of data, kept in root. You may choose more elegant sorting function, for example, parse a character tree into string.
3. Use binary search to locate the necessary sub-tree. You may quickly reject subtrees, with the number of nodes, not equal to the T2 number of nodes (or with the different depth).

Note that steps 1) and 2) must be done only once, then you can test many sub-tree candidates, using the same preprocessed result.

Reference - stackoverflow

Read More

Create linked lists of all the nodes at each depth for a BST

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/create-linked-lists-of-all-the-nodes-at-each-depth-for-a-binary-tree/.

Problem

Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)

Example
So a binary tree such as :

       (1)
      /   \
     /     \
   (2)     (3)
  /  \     / \
(4)  (5) (6) (7)

Will return linked lists:

(1) => NULL
(2) => (3) => NULL
(4) => (5) => (6) => (7) => NULL

Solution

Method 1 - Level order traversal
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.

public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList(
        BinaryTreeNode root) {
    int level = 0;
    ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>();
    LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>();
    list.add(root);
    result.add(level, list);
    while (true) {
        list = new LinkedList<BinaryTreeNode>();
        for (int i = 0; i < result.get(level).size(); i++) {
            BinaryTreeNode n = result.get(level).get(i);
            if (n != null) {
                if (n.getLeft() != null)
                    list.add(n.getLeft());
                if (n.getRight() != null)
                    list.add(n.getRight());
            }
        }
        if (list.size() > 0) {
            result.add(level + 1, list);
        } else {
            break;
        }
        level++;
    }
    return result;
}

Thanks.

Read More

Find if there is a path between two vertices in a directed graph

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/find-if-path-exists-in-directed-graph-problem/.

Problem :

Given a Directed Graph and two vertices in it, check whether there is a path from the first given vertex to second.

Solution

We have already seen solution to connectivity in undirected graph via bfs. Now lets see it on directed graph.

BFS to check the connectivity

public enum State {
    Unvisited, Visited, Visiting;
}
 
public static boolean search(Graph g, Node start, Node end) {
    LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack
    for (Node u : g.getNodes()) {
        u.state = State.Unvisited;
    }
    start.state = State.Visiting;
    q.add(start);
    Node u;
    while (!q.isEmpty()) {
        u = q.removeFirst(); // i.e., pop()
        if (u != null) {
            for (Node v : u.getAdjacent()) {
                if (v.state == State.Unvisited) {
                    if (v == end) {
                        return true;
                    } else {
                        v.state = State.Visiting;
                        q.add(v);
                    }
                }
            }
            u.state = State.Visited;
        }
    }
    return false;
}

Like wise we can also apply DFS.

public static boolean isRouteBetween(Digraph g, Integer start, Integer end) {
    Stack<Integer> stack = new Stack<Integer>();
    Set<Integer> visited = new HashSet<Integer>();
    if (start != null) {
        stack.push(start);
 
        while (!stack.isEmpty()) {
            Integer curr = stack.pop();
            if (!visited.contains(curr)) {
                if (curr.equals(end))
                    return true;
                else {
                    visited.add(curr);
                    for (Integer child : g.adj(curr))
                        stack.push(child);
                }
            }
        }
    }
    return false;
}

 Time complexity: O(|V|+|E|). Space complexity: O(|V|).


Use Stack for DFS. Use Queue for BFS.

Read More

How to check whether a given number n belongs to fibanocii series?

The standard way (other than generating up to N) is to check if (5N²+4) or (5N²−4) is a perfect square.

 Had discussion with my friend, on this and hence I thought its a good information to share via blog.

More - 

http://math.stackexchange.com/questions/9999/checking-if-a-number-is-a-fibonacci-or-not

Read More

Find next higher number using exact same digits

Problem

Given a number X find the number Y which is next higher number than X using the exact same digits as in X.

Example
For example: given 38276 return 38627

Solution

Method 1 - Brute force
The brute-force method is to generate the numbers with all digit permutations and consider all the higher numbers than the given number and return the minimum number from those higher numbers.

code -

int findNext(int n)
{
    int nextNum = INT_MAX;
    String nStr = Integer.toString(n);
     
    for(String perm : permutations(nStr)) {
        int pNum = Integer.valueOf(perm);
        if(pNum>n){
            nextNum = Math.min(pNum, nextNum);
        }          
    }
    if(nextNum == INT_MAX) {
        return -1;
    }
    else {
        return nextNum;
    }
}

Time complexity - O(polynomial)

Method 2 - Split the number and swapping the digits 

Consider the number X  =   989325321

1. Split the sequence of digits in two, such that the right sequence is as long as possible while remaining in decreasing order:
   

                              98932   5321

2. Take the last digit of the first sequence, and swap it with the smallest digit in the second that is bigger than it:
   

                              9893(2)   5(3)21
   

   
   After swapping 2 and 3
   

                              98933   5221
   

3. Sort the second sequence into increasing order:

                              98933   1225

   
   This is our number - the next higher number with same digits.
   

Time complexity - O(n), where n is number of digits


References

    Google Code Jam 2009 Round 1B

Read More

Stack of plates

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/stack-of-plates/.

Question 
Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

Solution

1. push(), to the last stack, if last full, create new stack. So, in a way, rather than stack overflow exception, return boolean if the stack is full.
2. pop(), pop from the last stack, if last is empty, then delete stack
3. popAt(int index), pop from “index”th stack, will ignore empty spaces to save time.

Code in java
(credits)

import java.util.ArrayList;
 
public class SetOfStacks{
    private int threshold;
    private ArrayList<MyStack> setOfStacks =new  ArrayList<>();
     
    SetOfStacks(int threshold) {
        this.threshold = threshold;       
    }
    //get the last stack
    public MyStack getLastStack(){
        int size = setOfStacks.size();
        if(size <= 0) return null;
        else return setOfStacks.get(size - 1);
    }
     
    //get the nth stack
    public MyStack getNthStack(int n){
        int size = setOfStacks.size();
        if(size <= 0) return null;
        else return setOfStacks.get(n - 1);
    }
     
    //push value
    public void push(int value){
        MyStack lastStack = this.getLastStack();
         
        if(lastStack == null){
            lastStack = new MyStack(threshold);
            lastStack.push(value);
            setOfStacks.add(lastStack);
        }else {
            if( !lastStack.isAtCapacity())
                lastStack.push(value);
            else {
                MyStack newLastStack = new MyStack(threshold);
                newLastStack.push(value);
                setOfStacks.add(newLastStack);
            }
        }   
    }
    // the pop
    public int pop(){
        MyStack lastStack = this.getLastStack();
        int v = lastStack.pop();
        if(lastStack.size() == 0) setOfStacks.remove(setOfStacks.size() -  1);
        return v;
    }
     
     
    //pop the nth stack
    public int pop(int nth){
         MyStack nthStack = this.getNthStack(nth);
         int v = nthStack.pop();
         if(nthStack.size() == 0) setOfStacks.remove(setOfStacks.size() -  1);
         return v;  
         
    }
     
    public String toString(){
        String s = "";
        for(int i = 0; i < setOfStacks.size(); i++){
            MyStack stack = setOfStacks.get(i);
            s = "||" + stack.toString() +  s;
        }         
        return s;
    }
     
     
    public static void main(String[] args){
        SetOfStacks stacks = new SetOfStacks(3);
        stacks.push(1);
        stacks.push(2);
        stacks.push(3);
        stacks.push(4);
        stacks.push(5);
        stacks.push(6);
        stacks.push(7);
        System.out.println("the stack is: " + stacks);
        stacks.pop(1);
        System.out.println("pop 1st: " + stacks);
        stacks.pop(2);
        System.out.println("pop 2nd stack: " + stacks);
        stacks.pop(1);
        System.out.println("pop 1st stack: " + stacks);
        stacks.pop(2);
        System.out.println("pop 2nd stack: " + stacks);
         
         
    }
}
 
//MyStack goes with size(), isAtCapacity()
//implemented from a array
 
class MyStack {
     
    private int top = -1;  
    private int[] buffer;
    private int capacity;
     
     
    MyStack(int capacity){
        this.capacity = capacity;
        buffer = new int[capacity];
    }
     
    public void push(int v){
        buffer[++top] = v;
    }
     
    public int pop(){
         
        return buffer[top--];
    }
    // if the stack is at capacity
    public Boolean isAtCapacity(){
        return capacity == top + 1;
    }
    //return the size of the stack
    public int size(){
        return top+1;
    }
     
    public String toString(){
        String s = "";
        int index = top;
        while(index >= 0){
            s += "[" + buffer[index--] + "]"+ " -> ";
        }
        return s;
         
    } 
}

TextBook notes:
What about the follow up question? This is a bit trickier to implement, but essentially we should imagine a “rollover” system. If we pop an element from stack 1, we need to remove the bottom of stack 2 and push it onto stack 1. We then need to rollover from stack 3 to stack 2, stack 4 to stack 3, etc.
NOTE: You could make an argument that, rather than “rolling over,” we should be OK with some stacks not being at full capacity. This would improve the time complexity (by a fair amount, with a large number of elements), but it might get us into tricky situations later on if someone assumes that all stacks (other than the last) operate at full capacity. There’s no “right answer” here; discuss this trade-off with your interviewer!

Read More

Implementing 2 stacks in an array

Problem: 
 How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space?


Lets denote the stacks by suffix 1 and 2. Now we have to implement the following methods :
push1(int x) –> pushes x to first stack
push2(int x) –> pushes x to second stack
pop1() –> pops an element from first stack and return the popped element
pop2() –> pops an element from second stack and return the popped element

Solution
Method 1 (Divide the space in two halves)
A simple way to implement two stacks is two divide the array in two halves and assign the half half space to two stacks, i.e., use arr[0] to arr[n/2] for stack1, and arr[n/2+1] to arr[n-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.
The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[]. For example, say the array size is 6 and we push 3 elements to stack1 and do not push anything to second stack2. When we push 4th element to stack1, there will be overflow even if we have space for 3 more elements in array.

Method 2 (A space efficient implementation)
This method efficiently utilizes the available space. It doesn’t cause an overflow if there is space available in arr[]. The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction.

Here is the code in java:

package com.vaani.ds.stack.impl;

public class TwoStacks {

 int[] arr;
 int size;
 int top1, top2;

 public TwoStacks(int n) // constructor
 {
  size = n;
  arr = new int[n];
  top1 = -1;
  top2 = size;
 }

 // Method to push an element x to stack1
 void push1(int x) {
  // There is at least one empty space for new element
  if (top1 < top2 - 1) {
   top1++;
   arr[top1] = x;
  } else {
   throw new IllegalStateException("Stack Overflow");
  }
 }

 // Method to push an element x to stack2
 void push2(int x) {
  // There is at least one empty space for new element
  if (top1 < top2 - 1) {
   top2--;
   arr[top2] = x;
  } else {
   throw new IllegalStateException("Stack Overflow");
  }
 }

 // Method to pop an element from first stack
 int pop1() {
  if (top1 >= 0) {
   int x = arr[top1];
   top1--;
   return x;
  } else {
   throw new IllegalStateException("Stack UnderFlow");
  }
 }

 // Method to pop an element from second stack
 int pop2() {
  if (top2 < size) {
   int x = arr[top2];
   top2++;
   return x;
  } else {
   throw new IllegalStateException("Stack UnderFlow");
  }
 }

 /* Driver program to test twStacks class */
 public static void main(String[] args) {
  TwoStacks ts = new TwoStacks(5);
  ts.push1(5);
  ts.push2(10);
  ts.push2(15);
  ts.push1(11);
  ts.push2(7);
  System.out.println("Popped element from stack1 is " + ts.pop1());
  ts.push2(40);
  System.out.println("\nPopped element from stack2 is " + ts.pop2());

 }
}

Output:

  Popped element from stack1 is 11
  Popped element from stack2 is 40

Time complexity of all 4 operations of TwoStacks is O(1).

3 stacks in an array is extended in a separate post.

Thanks.
.

Read More

Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/set-matrix-zeros-problem/.

Problem

Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and  column is set to 0

Example

Input : 

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

Output :

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

Solution

Method 1 - Using the extra space and O(n^2) solution
In this approach we can do :

1. Scan the matrix, store the numbers of rows and columns that will be set to zero to two sets
2. Iterate through those two sets and set corresponding row and col to zeros.

public static void setZero(int[][] matrix) {
    Set<Integer> rowToClear = new HashSet<Integer>();
    Set<Integer> colToClear = new HashSet<Integer>();
    for(int i = 0; i < matrix.length; ++i) {
        for(int j = 0; j < matrix[0].length; ++j) {
            if(matrix[i][j] == 0) {
                rowToClear.add(i);
                colToClear.add(j);
            }
        }
    }
     
    for(Integer row : rowToClear) {
        for(int j = 0; j < matrix[row].length; ++j) {
            matrix[row][j] = 0;
        }
    }
     
    for(Integer col : colToClear) {
        for(int i = 0; i < matrix.length; ++i) {
            matrix[i][col] = 0;
        }
    }
}

Time complexity - O(M*N) and space complexity O(M+N).

Also, as SET takes more space, rather than using SET, we can use a simple boolean arrays.

boolean[] rowBooleanVectors = new boolean[matrix.length];
boolean[] colBooleanVectors = new boolean[matrix[0].length];
for(int i = 0; i < matrix.length; ++i) {
    for(int j = 0; j < matrix[0].length; ++j) {
        if(matrix[i][j] == 0) {
            rowBooleanVectors[i] = true;
            colBooleanVectors[j] = true;
        }
    }
}
 
for(int i = 0; i < matrix.length; ++i) {
    for(int j = 0; j < matrix[0].length; ++j) {
        if( rowBooleanVectors[i] || colBooleanVectors[j])
            matrix[i][j] = 0;
    }
}

Time complexity - O(M*N) and space complexity O(M+N).

Method 2 -  Space efficient and O(n^2) solution
This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays rowBooleanArray[] and colBooleanArray[] of method 1.

So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary.

We now need 2 passes.

I use 1rst column and first row as markers to know where are rows/cols with only 1's. Then, there are 2 variables l and c to remember if 1rst row/column are all 1's also. So the first pass sets the markers and resets the rest to 0's.
The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on l and c.

arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).
1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 0s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 0s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

Here is the code:

N = matrix.length;
M = matrix[0].length;

// pass 1

// 1 rst line/column
int c = 1
for(int i = 0; i < N; ++i) {
    c &= matrix[i][0]
}

l = 1
for(int j = 0; j < M; ++j) {
    l &= matrix[0][i]
}


// other line/cols
// use line1, col1 to keep only those with 1
for(int i = 1; i < N; ++i) {//start iterating with 1
    for(int j = 1; j < M; ++j) {
        if (matrix[i][j] == 0){
            matrix[0][j] = 0
            matrix[i][0] = 0
  }
        else
            matrix[i][j] = 0
 }
}
// pass 2

// if line1 and col1 are ones: it is 1
for(int i = 1; i < N; ++i){
    for(int j = 1; j < M; ++j) {
        if( matrix[i][0] & matrix[0][j] == 1)
            matrix[i][j] = 1
 }
}

// 1rst row and col: reset if 0
if (l == 0){
    for(int i = 0; i < N; ++i) {
        matrix [i][0] = 0
 }
}
if (c == 0){
    for(int j = 1; j < M; ++j) {
        matrix [0][j] = 0
 }
}

print(matrix);

Time Complexity: O(M*N)
Auxiliary Space: O(1)

Reference

• http://stackoverflow.com/questions/339262/set-every-cell-in-matrix-to-0-if-that-row-or-column-contains-a-0

Read More

Rotate n * n matrix by 90 degrees

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/rotate-n-x-n-matrix-by-90-degrees/.

Problem

Rotate the n*n matrix by 90 degrees.

Another way to ask the same problem   

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Example

       Example 1                          Example 2
INPUT    >>     OUTPUT      |         INPUT    >>  OUTPUT  
                            |
4                           |             4                                         
                            |
1 2 3 4        1 1 1 1      |     11 12 13 14      41 31 21 11
                            |
1 2 3 4        2 2 2 2      |     21 22 23 24      42 32 22 12
                            |
1 2 3 4        3 3 3 3      |     31 32 33 34      43 33 23 13
                            |
1 2 3 4        4 4 4 4      |     41 42 43 44      44 34 24 14

Solution

Consider the array

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

Method 1 - Using 2D array of same size
Here we are

//runner method call
int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}

Lets understand this by example.
Consider the array :

Now, when i=0 and j=0, we insert matrix[n-1,0] to ret[0,0]

 Similarily we continue for i=0, and iterating over j.

Now, i=1,  and iterating over j :

Complexity
Time complexity - O(n^2)
Space complexity - O(n^2)

But as we are using lots of space, can we do better?


Method 2 - Without using any extra spaces but O(n^2)
This example is taken from here. Here is the basic algo:

1. Iterate over the 2D array with i and j iterators to the size of N/2
2. Now take the corner elements based on i and j, and swap them accordingly

Java Code

public static void rotate(int[][] matrix) {
    int N = matrix.length;
    for(int i = 0; i < N/2; ++i) {
        for(int j = 0; j < (N+1)/2; ++j) {
            int temp = matrix[i][j];  // save the top element;
            matrix[i][j] = matrix[N-1-j][i];  // right -> top;
            matrix[N-1-j][i] = matrix[N-1-i][N-1-j]; // bottom -> right;
            matrix[N-1-i][N-1-j] = matrix[j][N-1-i];// left -> bottom;
            matrix[j][N-1-i] = temp;                // top -> left;
        }
    }
}

Time complexity - O(n^2)
Space complexity - O(1)

Example
Consider the following matrix with N = 4

i=0,j=0 

Now we see that 1,4,13 and 16 are at the right place. Lets iterate further 
i=0,j=1

Similarly we will go on.
Finally we will get following :

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

So, to sum up we were doing this:

1           4


13          16

then we rotate the following diamond which is sort of askew

    2
            8
9       
        15

and then the 2nd skewed diamond

        3
5           
            12
    14

so that takes care of the outer edge so essentially we do that one shell at a time until
finally the middle square (or if it's odd just the final element which does not move)

6   7
10  11

so now let's figure out the indices of each layer, assume we always work with the outermost layer, we are doing

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

so on and so on until we are halfway through the edge
so in general the pattern is

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

Can we do better. It may not look obvious, but yes we can. Here is the next solution:

Method 3 - Adding decorator on the top of matrix
This method has been suggested by Drew here. Just keeping it here:

Whilst rotating the data in place might be necessary (perhaps to update the physically stored representation), it becomes simpler and possibly more performant to add a layer of indirection onto the array access, perhaps an interface:

interface IReadableMatrix
{
    int GetValue(int x, int y);
}

If your Matrix already implements this interface, then it can be rotated via a decorator class like this:

class RotatedMatrix : IReadableMatrix
{
    private readonly IReadableMatrix _baseMatrix;

    public RotatedMatrix(IReadableMatrix baseMatrix)
    {
        _baseMatrix = baseMatrix;
    }

    int GetValue(int x, int y)
    {
        // transpose x and y dimensions
        return _baseMatrix(y, x);
    }
}

Rotating +90/-90/180 degrees, flipping horizontally/vertically and scaling can all be achieved in this fashion as well.
Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.
As with all performance issues, measure, measure, measure!

Reference

• http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array

Read More

Determine if a string has all unique characters

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/determine-if-a-string-has-all-unique-characters/.

Problem:

Implement an algorithm to determine if a string has all unique characters.

Solution

Solution1 - My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop.

bool uniqueChars(string myString)
{
    for (int x = 0; x < myString.length(); x++)
    {
        for (int y = 0; y < myString.length(); y++)
        {
            if (myString[x] == myString[y] && x != y) return false;
        }
    }
    return true;
}

Time complexity - O^2
Space complexity - O(1)

Improvements
This code is very simple, but there are some problems. First, comparisons are repeated. Let's say we have a string of five characters, and the string is "ABCDE". On the first iteration, we will compare A to B, then to C, then to D, then to E. On the second iteration, we will compare B to A, then to C, then to D, then to D. Do you see how the comparison between A and B is repeated on the second iteration?

We can optimize this code a bit by altering the loops so that each character is only compared to every character AFTER it. This would mean that once A is compared to all the other characters, the other characters never compare themselves to A again.

bool uniqueChars(string myString)
{
    for (int x = 0; x < myString.length() - 1; x++)
    {
        for (int y = x + 1; y < myString.length(); y++)
        {
            if (myString[x] == myString[y]) return false;
        }
    }
    return true;
} 

Time complexity - O(n^2)...still bad

Solution 2 - Using the 256 length array assuming the string is an ascii character

1. Create an int array [0-255], one for each character index, initialised to zero.
2. Loop through each character in the string and increment the respective array position for that character
3. If the array position already contains a 1, then that character has already been encountered. Result => Not unique.
4. If you reach the end of the string with no occurrence of (3), Result => the string is unique.

Here is the function in java

public boolean uniqueChars(String s) {
    boolean[] mask = new boolean[256];
    for (int i = 0; i < s.length(); i++) {
        if (mask[s.charAt(i)])
            return false;
        mask[s.charAt(i)] = true;
    }
    return true;
}

Solution 3 - Sorting the array and then finding unique chars

Here using the sorting algorithm to sort the string first, then compare every pair of neighboring characters to see if they are the same.  The main time consuming are sorting array + neighborhood comparisions. But based on the document I searched online, the sorting function in Java uses merge sort or quicksort, which depends on the data type, also for efficiency, it would switch to insertion sort when fewer than seven array elements are being sorted. So, in general,
Time: O(nlgn), n is the length of string.

public boolean uniqueChars(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    for (int i = 0; i < chars.length - 1; i++) {
        if (chars[i] == chars[i + 1])
            return false;
    }
    return true;
}

What if not use additional data structure?

Solution1 and solution 3 still work here. But in the interview if someone gives you a restricted string which can have only say 'a' and 'z' and asks you to not use any data structure then?

Solution 4
For this solution, the condition is very limited. Here I use a mask to keep the occurrence of characters with corresponding bits. E.g. 'a' occurrence will be stored at bit 0, while 'c' occurrence will be stored at bit 2. So, if mask is 4, that means 'c' has appeared before, and only 'c' has appreared. But the cons of this approach is its limited the input string could only contain continuous and easy handling characters, while the length of these characters could not be larger than log2(MAX_INT or MAX_LONG). Here, the integer value is 32-bit, so we could have this approach.

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

Understanding the code here.

int checker is used here as a storage for bits. Every bit in integer value can be treated as a flag, so eventually int is an array of bits (flag). Each bit in your code states whether the character with bit's index was found in string or not. So, lets consider a, it is no 1st bit set, C will have 3rd bit set and so on.
00000000000000000000000000000001 a 2^0
00000000000000000000000000000010 b 2^1
00000000000000000000000000000100 c 2^2
00000000000000000000000000001000 d 2^3
--------------------------------------so on
00000001000000000000000000000000 y 2^24
00000010000000000000000000000000 z 2^25

Initially checker is equal to 0 i.e.
checker=00000000000000000000000000000000

Consider the string ayza
To, begin with we will have a as char,
a= 00000000000000000000000000000001

checker='a' or checker
checker=00000000000000000000000000000001
a and checker=0 no dupes condition

string 'az'
checker=00000000000000000000000000000001
z =00000010000000000000000000000000
z and checker=0 no dupes


checker=z or checker= 00000010000000000000000000000001
string 'azy'
checker=00000010000000000000000000000001
y =00000001000000000000000000000000
checker and y=0 no dupes condition

checker= checker or y =00000011000000000000000000000001
string 'azya'
checker= 00000011000000000000000000000001
a= 00000000000000000000000000000001
a and checker=1 we have a dupe


 You could use bit vector for the same reason instead of int. There are two differences between them:

• Size. int has fixed size, usually 4 bytes which means 8*4=32 bits (flags). Bit vector usually can be of different size or you should specify the size in constructor.
• API. With bit vectors you will have easier to read code, probably something like this:
  vector.SetFlag(4, true); // set flag at index 4 as true
  for int you will have lower-level bit logic code:
  checker |= (1 << 5); // set flag at index 5 to true

Also probably int may be a little bit faster, because operations with bits are very low level and can be executed as-is by CPU. BitVector allows writing a little bit less cryptic code instead plus it can store more flags.
For future reference: bit vector is also known as bitSet or bitArray. Here are some links to this data structure for different languages/platforms:

• CPP: BitSet
• Java: BitSet
• C#: BitVector32 and BitArray

Read More