Monthly Archives: September 2013

Given an array, find two values in the array which sum upto a value K

Given an array, and a value K as input, we have to find a pair of elements such that their sum is K.

There are multiple ways  of solving this problem. We will discuss some of them in this post. Let us implement the function which prints the two values such that array[i] + array[j] = K if there is such a pair exists. If not print “No such pair”.

Method#1: Brute-Force approach

Check each possible pair of values from this array to see if their sum is K. The Java function for this algorithm is given below.

 public static void printTwoValues(int[] array, int sum)
{
int i,j;
for( i = 0; i < array.length - 1; i++ )
{
for( j = i+1; j < array.length; j++ )
{
if( array[i] + array[j] == sum )
{
System.out.println("The two values are (" + i +", " + j + ")");
return;
}
}
}
System.out.println("No such pair exists!");
}

This algorithm runs in O(n2) time complexity and O(1) space complexity.

Method#2: Sorting Approach
This method will modify the sequence of elements in the array as we sort the array first. 
Take two indices one pointing to the beginning and the other pointing to the end of the array. Calculate the sum of these two values and check if it is the given value K. If it is, print the two values and return.
Otherwise check if their sum is greater then given value K, then we need to decrement the second pointer as we are exceeding the target value.
Similarly if the sum is lesser than given value K, we need to increment the first pointer hoping that we move closer to the required sum.

public static void printTwoValues(int[] array, int sum)
{
Arrays.sort(array);
int i = 0;
int j = array.length-1;
while( i < j)
{
if( array[i] + array[j] == sum)
{
System.out.println("The two values are (" + array[i] +", " + array[j] + ")");
return;
}
else if( array[i] + array[j] < sum )
{
i++;
}
else
{
j--;
}
}
System.out.println("No such pair exists!");
}

This algorithm runs in O(n log n) time complexity as we are sorting the array first and O(1) space complexity.

Method#3: Hash set approach
This method uses an implementation of the set data structure to store the values. As we run through the array, we search the set for (sum-array[i]). If it is found, we are done. Otherwise we insert array[i] into the set.

public static void printTwoValues(int[] array, int sum)
{
HashSet<Integer> hSet = new HashSet<Integer>();
int i;
for( i = 0; i < array.length; i++ )
{
if( hSet.contains(sum-array[i]) )
{
System.out.println("The two values are (" + array[i] +", " + (sum-array[i]) + ")");
return;
}
else
hSet.add(array[i]);
}
System.out.println("No such pair exists!");
}

This algorithm takes O(n) time but uses O(n) extra space for the set data structure. 

Variations of the problem: 

  • However if the problem is to find the two indices i,j such that array[i] + array[j] = K, the first and third approaches can easily be modified to solve this problem. But the second approach which uses sorting can not be used because the order of the elements gets changed. 
  • If the problem is to find all pairs whose sum is K, and the array may contain duplicates, first approach does not change. But the sorting approach will not work.

We will discuss these problems in the upcoming posts.

Checking duplicates in an array in O(n) time and O(1) space

Let us consider an array of size N contains numbers in the range [1,N]. We have to find if it has duplicates in linear time – O(n) and by using only constant extra space – O(1). 

Let us also have a restriction that we should traverse the array only once. Take a look at the following algorithm.

When traversing through the elements of the array, we consider each element as an index into the same array and negate the value at that index. If we already find a negative value at this index (i.e we have already seen this element), we can say that the array has duplicates.

Let us see understand this algorithm with a small example. The following table gives a snapshot of the array in each iteration.



Iteration
Array
1
Index
0
1
2
3
4
5
6
7
8
9
Value
5
1
3
2
-1
4
9
6
8
7
2
Index
0
1
2
3
4
5
6
7
8
9
Value
-5
1
3
2
-1
4
9
6
8
7
3
Index
0
1
2
3
4
5
6
7
8
9
Value
-5
1
-3
2
-1
4
9
6
8
7
4
Index
0
1
2
3
4
5
6
7
8
9
Value
-5
-1
-3
2
-1
4
9
6
8
7
5
Index
0
1
2
3
4
5
6
7
8
9
Value
-5
-1
-3
2
-1
4
9
6
8
7

In this example the range is [1,10]
Since the array values are in the range [1,N] and the array stores the values from [0,N-1] we are using index-1 to locate the element to be negated

In the first iteration value is 5, array[4] is negated.
In the second iteration value is 1, array[0] is negated
In the third iteration value is 3, array[2] is negated
In the fourth iteration value is 2, array[1] is negated
In the fifth iteration value is 1 again, We are supposed to make array[0] negative, but we found that it is already negative. Hence we can conclude that it has duplicates.

Here is the Java Implementation.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/13/13
* Time: 11:48 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array1 = {5,1,3,2,10,4,6,8,9,7};
if( hasDuplicates(array1) )
System.out.println("Array has duplicates");
else
System.out.println("Array does not have duplicates");

int[] array2 = {5,1,3,2,1,4,6,8,4,7};
if( hasDuplicates(array1) )
System.out.println("Array has duplicates");
else
System.out.println("Array does not have duplicates");
}
public static boolean hasDuplicates(int[] array)
{
for(int i = 0; i < array.length; i++ )
{
//take the absolute value because it might have been negated by some previous
//operation
int index = Math.abs( array[i] ) - 1;
//If array[index] is negative; we have a duplicate, return true
if( array[index] < 0 )
return true;
else // array[i] is found first time, negate array[ array[i] ]
array[index] = -array[index];
}
return false;
}
}

Implementing Stack with GetMin operation

In this post we discuss how to efficiently implement a stack data structure with one additional operation getMin() along with push() and pop(). getMin() returns the minimum value in the stack.

The trick here is to use another stack which stores the minimum values of the original stack. The top of Min-stack always contains the minimum of stack elements so far inserted.

The Push operation is implemented as follows.
When an element is pushed on to the stack, we have to compare that with top of min-stack. If the new element is minimum, We have to push that element onto the min-stack too. We need not push that element on to min-stack if it is not lesser than top of min-stack.

The Pop operation is implemented as follows.
While popping the element from the original stack, we should also make sure that if minimum element is popped, it should also be removed from Min-stack.

The following table explains the logic.



Operation
Stack
Min-stack
Description
Push(5)
5
5
5 pushed on to both the stacks
Push(2)
5 2
5 2
2 is pushed to both stacks
Push(3)
5 2 3
5 2
3 is not pushed to min-stack because it is not minimum
Push(1)
5 2 3 1
5 2 1
1 is pushed to both because it is new minimum
Pop()
5 2 3
5 2
1 is popped from both because it is minimum
Pop()
5 2
5 2
No need to pop from min-stack because 3 is not minimum

  
Observe that top of min-stack always contains the minimum element.

Following is the Java code which implements the above approach.

import java.util.Stack;

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/4/13
* Time: 7:04 AM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
MinStack mStack = new MinStack();
mStack.push(5);
System.out.println(mStack.getMin());
mStack.push(2);
System.out.println(mStack.getMin());
mStack.push(3);
System.out.println(mStack.getMin());
mStack.push(1);
System.out.println(mStack.getMin());
mStack.pop();
System.out.println(mStack.getMin());
mStack.pop();
mStack.pop();
System.out.println(mStack.getMin());
}
static class MinStack
{
Stack<Integer> dataStack;
Stack<Integer> minStack;
public MinStack()
{
dataStack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int d)
{
//Push that element to the original stack
dataStack.push(d);
//If either Min-stack is empty or
// newly inserted element is lesser, push it into min-stack also
if( minStack.empty() || d < minStack.peek())
{
minStack.push(d);
}
}
public int pop()
{
//pop the element from the original stack
int res = dataStack.pop();
//If the popped element is also the minimum,
//pop from the min-stack also
if( res == minStack.peek() )
{
minStack.pop();
}
return res;
}
//This function simply returns the top of min-stack
public int getMin()
{
return minStack.peek();
}
}
}

Check if an array has duplicate numbers

Given an array numbers, how do we write a function checkDuplicates() which returns true if the array has at least one element repeated; returns false if all the elements are unique.

We discuss three different implementations of this function with various time and space complexities.

Method-1: Naive approach

This approach checks every possible pair in the array to see if there are any duplicates. This is exhaustive  search and we can find the answer in O(n2) time. Because there are n(n-1)/2 possible pairs for an array of size n.

Time complexity: O(n2)
Space complexity: O(1)

The following is the C++ function which implements this approach.

 
bool checkDuplicates( int array[], int n)
{
int i,j;
for( i = 0; i < n; i++ )
{
for( j = i+1; j < n; j++ )
{
if( array[i] == array[j] )
return true;
}
}
return false;
}
 
Method-2: Sorting Approach
First sort the array using any sort which runs in O(n log n) time ( Quick sort/ Heap sort/ Merge sort).
Then all the duplicate elements comes together. Then simply compare all the adjacent elements to see if there are any duplicates.

Time complexity: O(n log n)
Space complexity: O(1) 

The following is the C++ function which implements this approach.
 

bool checkDuplicates( int array[], int n)
{
std::sort( array, array+n);
int i;
for( i = 0; i < n-1; i++)
{
if( array[i] == array[i+1] )
return true;
}
return false;
}
Method-3: Set/HashTable approach
Use a data structure like a Set or a Hash Table which keeps track of the elements. When trying to insert into these data structures, we can see if the element already exists; If the element already exists in the data structure, we say that the array has duplicates.

Time complexity: O(n)
Space complexity: O(n)

The following is the Java function which implements this approach.

public static boolean checkDuplicates(int [] array)
{
HashSet<Integer> hSet = new HashSet<Integer>();
for( int i = 0; i < array.length; i++ )
{
if( !hSet.add(array[i]) )
return true;
}
return false;
}

How does Quicksort work?

Quick sort is a comparison based sorting algorithm. Like Merge sort, this also follows divide and conquer algorithmic pattern.

Quick sort works as follows. 

A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the elements to the left of pivot ( left part) must be less than or equal to pivot, and all the elements to the right of pivot( right part) must be greater than pivot.

At this point it is easy to understand that the pivot element is in it’s position and only left, and right parts needs to be sorted. We use recursive call to sort these parts.

Here partition process is the key to sorting. 

Consider the following example to understand the partitioning process.

Initial array: 4 is chosen as pivot for simplicity


4
7
3
6
9
2
8
5
1


After partitioning:


2
1
3
4
9
6
8
5
7

 
You can get a good understanding of the whole procedure if we look at the following animation (Image courtesy: Wikipedia).

Here is the C++ code for quick sort.This procedure runs in O(n log n) time in average case. But in the worst case, It can take up to O(n^2) time.

 
#include <iostream>

using namespace std;

void quick_sort(int[], int, int);

int main()
{
int array[] = {4,7,3,6,9,2,8,5,1};
quick_sort(array,0,8);
for( int i = 0; i < 9; i++ )
{
cout<<array[i]<<" ";
}

return 0;
}

void quick_sort(int array[], int l, int h)
{
if( l < h)
{
int left = l; //starting index of the array
int right = h;// ending index of the array
int pivot = array[left];//take left most element as pivot

while ( left < right)
{
//decrement right pointer as long as the element
//at this index is greater than pivot
while ( array[right] > pivot )
right--;
//increment left pointer as long as the element
//at this index is less than or eqal to pivot
while ( array[left] <= pivot )
left++;

//swap the elements if left and right do not overlap
if( left < right)
{
swap( array[left], array[right] );
}
}

//right is the correct position for pivot,
//so swap the first element(chosen as pivot) with 'right'
swap(array[l],array[right]);

//recursively call quick sort for left and right parts
quick_sort(array, l, right-1);
quick_sort( array, right+1,h);

}
}

How does a merge sort work?

Merge sort follows the divide and conquer approach. This is also a comparison based sorting algorithm like Bubble sort, selection sort and insertion sort etc.

In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just one element i.e no need to sort an array with just one element.

For example let us consider an array of 5 elements
[3,2,1,5,4]

It is divided into two sub-arrays [3,2,1] and [5,4]. We apply merge sort recursively on both the sub-arrays and merge them to become a single sorted array.

Here is how the first sub-array gets sorted.
[3,2,1] is divided into [3,2] and [1]. No need sort the second sub-array because it just contains one element.
[3,2] is divided into [3], [2].

The merge procedure combines the arrays [3], [2] into sorted sub-array [2,3].

Then the sub-array [2,3] is merged with [1] to become [1,2,3]

Finally [1,2,3] gets merged with [4,5] to become [1,2,3,4,5] which is fully sorted.

The merge procedure works as follows. The input to the merge procedure is two sorted sub-arrays. 

We initialize two pointers to the first elements of two sub-arrays. We copy the lesser element among them to a temporary array and advance the corresponding pointer to the next element. We repeat this procedure until atleast one of the sub-arrays becomes empty.

Finally we copy the non-empty sub-array elements to the temporary array.

Here is the Java implementation of merge sort. 

public class Main {
public static void main(String[] args)
{
int [] array = {51,126,98,12,3,34,269,73,6,88};
mergeSort( array, 0, array.length-1);
for( int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
}
public static void mergeSort(int[] array, int left, int right )
{
if( left < right)// If the array has at least one element
{
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid+1, right);
merge(array, left, mid+1, right);
}
}
public static void merge(int [] array, int l, int m, int r)
{
//We need a temporary array of size r-l+1 for the merged elements
int [] temp = new int[r-l+1];
int i = l; //index of first sub-array
int j = m; //index of second sub array
int k = 0;
while( i < m && j <= r)
{
if( array[i] < array[j])
{
temp[k++] = array[i++];
}
else
{
temp[k++] = array[j++];
}
}
//copy if there are any elements remaining in any half
while( i < m )
{
temp[k++] = array[i++];
}
while ( j <= r )
{
temp[k++] = array[j++];
}
//copy sorted elements from temp to original array
for( i = l,j=0 ; i <= r; i++,j++)
{
array[i] = temp[j];
}
}

} 
 
 

This code runs in O(n log n) time in the worst case also. But it is not an in-place sorting mechanism because we use a temporary array in the merge procedure.