Category Archives: Java

Printing biggest elements to its right in an array

Given array of elements we have to write a program to print the biggest element to it’s right for each of the elements in the given array.

For example let us consider the array {3, 9, 2, 4, 6, 1}.

The output for this array should be {9, 6, 6, 6, 1, -1}. As a convention, we print -1 for the last element because there are no elements to it’s right.

This problem can be solved in O(n) time and O(1) space by using the following algorithm.

Start from the end of the array. print -1 for the last element. Use a variable to keep track of the greatest element found so far while traversing backwards and fill the entries with this variable.

Here is the Java program to do this.

Alternative arrangement of numbers in the array

Given an array of 2n numbers of the following format
{a1, a2, a3,…an, b1, b2, b3, …bn}
We have to write a program to transform this into the following format.
{a1, b1, a2, b2, a3, b3, …, an, bn}

This can be done using the following algorithm. 
We iterate over the array for (n-1) times. In first iteration we swap the middle pair. In the second iteration we swap two of the middle pairs, and so on.

For example let us consider an array of 6 numbers {1,3,5,2,4,6}. Here is how the array is changed while traversing through the algorithm.

1  3  5 <-> 2  4  6
1  3 <-> 2  5 <-> 4  6
1  2  3  4  5  6

Since n = 3, the algorithm iterated just two times and a total of 3 swaps.To generalize, for some arbitrary n, there will be (n2+2*n) / 8 swap operations performed. So it’s time complexity is O(n2) and space complexity is O(1). 

Finding a number in a sorted array with the least difference from given number

Given a sorted array and a value, we have to find the closest value (with least difference).
For example let the input array be {-2, 4, 7, 11, 17} and the input number is 10, the output should be 11.

This problem is actually a variation of binary search where in we have to find out the closest value found the array. If the given value exists in the array, we have to return that.

A sorted array and binary search gives a hint that we can solve this problem in O( log n) complexity. Here is how we can modify the binary search algorithm to solve this problem.

As in binary search algorithm, we try to search for the given number in the middle of the array. If the element is found, we just return it, because we got the least difference i.e 0.

We also maintain two variables one to store the minimum difference found so far (minDiff), and the other (result) to store the corresponding number. In each iteration, we find the difference between the given value and middle value. If this is lesser than minimum difference, we update the two variables.

At the end of the search we have the required number in the result variable.

Below is the Java code which implements the above algorithm.

Moving zeroes to the end of array

Given an array of elements which contains some zeros in between, we have to write a program to move all zeros to the end without disturbing the original order of the elements.

For example if the input is {0, 6, 2, 0, 0, 3, 1, 0, 4, 5, 0}, the output should be {6, 2, 3, 1, 4, 5, 0, 0, 0, 0, 0}

The algorithm is simple, we take two  indices , one to loop through the entire array, and another to keep track of the non-zero elements. Once we loop through all the elements, we can fill the remaining spaces with zeros.

This algorithm scans the input array only once and hence runs in O(n) time and does not take any extra space O(1).

Here is the Java code to do this.

Printing last K lines from a file

Given a large file containing many lines of text, How do we write an efficient program to print last k lines from that file.
One obvious approach is to read the entire file first to find the number of lines (n). In the second iteration skip first (n-k) lines, and print the remaining k lines. 
However, this approach might be prohibitively costly as the file is very big and disk operations are slow. More over, we are reading the file twice.
We can design an efficient solution if we take a buffer of size k and keep filling the buffer with the lines read from the file in a circular fashion. This is a type of page replacement algorithm often used in operating systems. If the buffer is full, we replace the oldest entry in the buffer with the new entry.
Once k lines are read from the file, we wrap around, and go back to the beginning of the buffer and overwrite the previous entries as they are no longer the last  k lines. 

Following is the java implementation of the above algorithm.

Finding the majority element of an array

Given an array of  N elements, the majority element is defined as the one which occurs more than N/2 times.

One simple approach is to find the mode (which appears for most number of times) and check if its frequency is greater than N/2.

Three strategies for finding the mode are discussed in my previous post. The best one among them, the hash map approach takes O(n) time and O(n) space.

We can solve this program even better by using Moore’s voting algorithm. This takes O(n) time and O(1) space.

This algorithm tries to find out the majority number in two iterations. In the first iteration, a probable candidate for majority number is found. In second iteration, we check if the candidate is really the majority number by counting it’s frequency.

The first iteration works as follows. We initialize the first element as the majority number and the count variable is initialized with 1. During further iterations, if the element is equal to majority number, we increment the count, otherwise we decrement the count. If at any point, the count reaches zero, We reassign the majority number to the current element and assign 1 to count.

For example, let us consider the input array {6, 2, 3, 6, 3, 6, 6, 6}. The following table explains the logic.

Iteration# 1 2 3 4 5 6 7 8
Data 6 2 6 6 3 6 1 6
Majority 6 2 6 6 6 6 6 6
count 1 1 1 2 1 2 1 2

At the end 6 is the candidate for majority number. In the second iteration we check the frequency of 6. If it is more than half of the array size it is the majority element.
 
Here is the Java implementation of this approach.

Inserting an element into a sorted linked list

Given a sorted linked list, how do we insert data into the list in proper order?
This is nothing but a step in insertion sort. Simply iterate through the elements to find the position for given number and insert at that position.
Here is the Java code to do that. I have used the LinkedList class available in java utilities so that we need not implement the entire linked list class on our own.

import java.util.LinkedList;
import java.util.ListIterator;

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/11/13
* Time: 5:32 AM
* To change this template use File | Settings | File Templates.
*/
public class SortedListDemo {
public static void main(String[] args)
{
LinkedList<Integer> sortedList = new LinkedList<Integer>();

sortedInsert(sortedList, 3);
sortedInsert(sortedList, 1);
sortedInsert(sortedList, 6);
sortedInsert(sortedList, 4);
sortedInsert(sortedList, 2);
sortedInsert(sortedList, 5);

System.out.println("Contents of the sorted list: " + sortedList);
}
public static void sortedInsert(LinkedList<Integer> sList, int data)
{
int pos = 0;

for(int listData : sList )
{
if( listData > data)
break;
pos++;
}

//Alternative code for the above loop using an iterator
/*
ListIterator<Integer> listIterator = sList.listIterator();
while( listIterator.hasNext() && listIterator.next() < data )
pos++;
*/
//insert the data in its correct position
sList.add(pos, data);
}
}

How does a counting sort work?

Counting sort as its name indicates sort a list of integers by counting the occurrence each number appearing in the list. This is possible when the range of integers (particularly small) is given.

Unlike comparison based sorting algorithms which run in O( n log n) time in the worst case, Counting sort runs O(n) time.

For example let us assume the range of numbers is 0-4. and we have an input array as follows.


3
0
3
2
4
0
2
1
2
4

This is basically integer sorting algorithm where in 
  1. The first iteration it counts the frequency of each number appearing the list. These counts are stored in an array indexed by the numbers itself. 
  2. In the second iteration, it counts the prefix sum array by counting how many numbers that are less than or equal to that number.
  3. The third iteration places the numbers in the correct place based on their frequency.
Count array


Index
0
1
2
3
4
Counts
2
1
3
2
2
Prefix Sum
2
3
6
8
10

  

 You can take a look at this animation for understanding counting sort better.

The following Java program implements the above approach.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/10/13
* Time: 5:29 AM
* To change this template use File | Settings | File Templates.
*/
public class CountingSortDemo {
public static void main(String[] args)
{
int[] numArray = {3,0,5,9,6,2,4,5,4,1};
int[] sortedArray = countingSort( numArray );
for( int i = 0; i < sortedArray.length; i++ )
{
System.out.print( sortedArray[i] + " ");
}
}
//Counting sort method
public static int[] countingSort(int [] array )
{
int[] sortedArray = new int[array.length];
int[] countArray = new int[10]; //For simplicity Assume the range 0-9
int i;
for( i = 0; i < array.length; i++ )
{
countArray[ array[i] ]++;
}
//calculate the prefix sums
for( i = 1; i < countArray.length; i++ )
{
countArray[i] += countArray[i-1];
}
//place the elements in the sorted array
for( i = 0; i < array.length; i++ )
{ 
            //Get the index to place into sorted array 
            int cIndex = countArray[ array[i] ];

sortedArray[cIndex-1] = array[i];
//decrement the frequency so that the same number is placed next
            //to previous entry 
countArray[ array[i] ]--;
}
return sortedArray;
}

}

This code is generic to sort any array objects with integer keys. If we just want to sort the array, we can combine the last two loops where we can fill the array with count of each number in order. You can do this by the following loop. 

int resIndex = 0;
for( i = 0; i < countArray.length; i++ )
{
for( int j = 0; j < countArray[i]; j++)
sortedArray[resIndex++] = i;
}

Maximum sum sub-array

Given an array of positive and negative values. We have to find the maximum sum a sub-array can have.

For example the the array {-1, 7, -2, 4, -3, -9, 2} has a maximum sum of 9 which corresponds to the sub-array {7, -2, 4}.

To solve this problem, we take two variables to keep track of running sum and maximum sum. While iterating through the array, we keep adding the elements to the running sum. If the running sum exceeds the maximum sum, we update the maximum sum to reflect the latest maximum. If it becomes negative we reset it to zero. At the end of the iteration maximum sum variable contains the required value.

If all the elements are negative, then this program gives an output of 0 (basically the sum of zero-length sub-array). This program runs in O(n) time and O(1) space.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 9/25/13
* Time: 10:45 PM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
int[] array = {-1, 4, -2, 3, 0, -5, 1, 2};
System.out.println("Maximum sum of sub-array is " + getMaxSum(array));
int[] array1 = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum sum of sub-array is " + getMaxSum(array1));
}
public static int getMaxSum(int[] array)
{
int maxSum = 0;// to keep track of maximum sum
int curSum = 0;// running sum
int i;
for( i = 0; i < array.length; i++ )
{
curSum += array[i];

if( curSum < 0 ) //reset if sum becomes negative
{
curSum = 0;
}

if( maxSum < curSum ) // update maxSum
maxSum = curSum;
}
return maxSum;
}
}

Maximizing stock profit / Finding the maximum difference in array

Given an array of numbers which indicates the prices of stocks for a period of time. We have to find the two values in the array such that their difference is maximum and also the greater value must appear later than smaller value.
In another way, we have to find the buying and selling price of the stock so that we get maximum profit.

For example  for the following array we can make a profit of 6 if you buy the stock @ 1 and sell it @ 7

[4, 8, 1, 5, 7, 6]

We can always find the correct solution if we try to examine each possible pair. This method is based on my previous post. It runs in O(n2) time.

But we want to design a linear time solution (i.e. O(n) ) and constant space (O(1)).

Here is how our algorithm works. We start from the end of the array and keep track of the maximum value encountered so far. We also find the difference between the current element and the maximum element. If the difference is greater than previous difference, we will update it.

Here is the Java implementation of the above solution. This approach takes O(n) time and iterate through the array only once. We assume that the array contains at least two elements. This program returns 0 if the stock prices in decreasing order.

/**
* Created with IntelliJ IDEA.
* User: Ravi
* Date: 10/1/13
* Time: 12:01 AM
* To change this template use File | Settings | File Templates.
*/
public class Main {
public static void main(String[] args)
{
//int[] stockPrice = {3,1,2,6,8,7,9,4,5};
//int[] stockPrice = {2, 3, 10, 6, 4, 8, 1};
int[] stockPrice = { 7, 5, 4, 6, 3, 2};
System.out.println( getMaxProfit(stockPrice) );
}
//Returns the max profit you can make for the given stock prices
//Assumes that there are at least 2 entries
public static int getMaxProfit(int[] price)
{
int maxProfit = 0;
//Init the max price with last item
int maxPrice = price[price.length-1];

for( int i = price.length - 2; i >= 0; --i )
{
int profit = maxPrice - price[i];

//update the maximum profit
if( profit > maxProfit )
maxProfit = profit;

//update the maximum price
if( price[i] > maxPrice )
maxPrice = price[i];
}
return maxProfit;
}
}