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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Created with IntelliJ IDEA. | |
| * User: Ravi | |
| * Date: 10/17/13 | |
| * Time: 6:01 AM | |
| * To change this template use File | Settings | File Templates. | |
| */ | |
| public class BiggestElementsRight { | |
| public static void main(String [] args) | |
| { | |
| int[] array = { 8, 7, 9, 4, 5, 6, 3, 1, 2}; | |
| int[] bigRight = getBiggestRight(array); | |
| for( int i = 0; i < bigRight.length; i++ ) | |
| { | |
| System.out.print( bigRight[i] + " "); | |
| } | |
| } | |
| public static int[] getBiggestRight(int[] array) | |
| { | |
| int i; | |
| int len = array.length; | |
| int[] bigArray = new int[len]; | |
| //Right most element does not have any biggest elements to its right; so put -1 | |
| bigArray[ len - 1] = -1; | |
| //start with last but one element assuming last element as the biggest | |
| int biggestNum = array[ len - 1 ]; | |
| for( i = array.length - 2; i >= 0; i-- ) | |
| { | |
| if( array[i+1] > biggestNum ) | |
| biggestNum = array[i+1]; | |
| bigArray[i] = biggestNum; | |
| } | |
| return bigArray; | |
| } | |
| } |
by