CODEWITHSUNDEEP
javaarraysalgorithm
techPackets
techPackets

Reputation: 4504

Find the least greater element on the right

I am trying to solve an algorithm wherein I have to find the least greater element on the right of an array reference

For an instance in the below array Input: [8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]

The least greater element on the right for the first element 8 is 18, for the second element 58 is 63 & so on. I need help with the logic to solve the algorithm. I intend to first solve with with brute force with a complexity of O(n^2).

The code I've written till now is below 

public class Tmp {

public static void main(String[] args) {

    int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 };
    int[] tmpArr = new int[arr.length];
    int pos = 0;
    int k=0;

    for (int i = 0; i < arr.length-1; i++) { 
        //int next = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            if ((arr[j] > arr[i])) {
             tmpArr[k]=arr[j]; // take all the values to the right of the element which are greater than it
             k++;
            }
        }

I've created the second array tmpArr to take all the values on the right of an element which are greater than an it. Probably sort that array then & take the first value. But that logic doesn't seem ok to me.

Another solution can be 

for (int i = 0; i < arr.length-1; i++) { 
    int leastGreater = ? //Don't know what to initialize with
            for (int j = i + 1; j < arr.length; j++) {
                if ((arr[j] > arr[i])) {
                   if(arr[j]<leastGreater){
                 leastGreater = arr[j];
                  }
                }
            }

Can anyone help with a simpler solution?

Upvotes: 1

Views: 2117

Answers (8)

18sit43 Siva
18sit43 Siva

Reputation: 1

what if the array is cirular form

Given a circular integer array nums .return the next greater number for every element in nums.

`Input=[9,1,2,4,3,5,8]

 Output=[-1,2,3,5,4,8,9]

9->-1 
1->2
2->3
4->5
3->4
5->8
8-9

Upvotes: -1

HARIPRAKASH
HARIPRAKASH

Reputation: 1

public class code44 {
public static void main(String[] args){
    int[] arr = {1,9,7,56,36,91,42};
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        int min = -1;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i]) {
                if (min == -1) {
                    min = arr[j];
                } else {
                    min = min > arr[j] ? arr[j] : min;
                }
            }
        }
        arr[i] = min;
    }
    for(int i =0; i < 7; i++)
        System.out.print(arr[i] + " "); 
    }
}

(or)

import java.util.Scanner;

class code4{
    public static int MAX = 10000;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] array = {1, 9, 7, 56, 36, 91, 42};

        for(int i = 0; i < 7; i++){
            int min = MAX;

            for(int j = i + 1; j < 7; j++){
                if(array[j] >= array[i] && min > array[j]){
                    min = array[j];
                }
            }
            array[i] = min != MAX ? min : -1;
        }

        printArray(array, 7);
        sc.close();
    }

    public static void printArray(int[] array, int n){
        for(int i = 0; i < n; i++){
            System.out.print(array[i] + " ");
        }
    }
}

input : 1, 9, 7, 56, 36, 91, 42 output : 7, 36, 36, 91, 42, -1, -1

Upvotes: 0

Loki
Loki

Reputation: 801

This should work

int a[] = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
    int n = a.length;
    for (int i = 0; i < n-1; i++){
        int diff = Integer.MAX_VALUE;
        int leastGreater = Integer.MAX_VALUE;
        for (int j = i+1; j < n; j++){
            if(a[j] - a[i] > 0 && diff > a[j] - a[i]){
                diff = a[j] - a[i];
                leastGreater = a[j];
            }
        }
        if (leastGreater == Integer.MAX_VALUE){
            System.out.println("Not Found for index " + i);
        }else {
            System.out.println(leastGreater + " found for index " + i);
        }
    }

It checks for difference to the right of current element which should be > 0 i.e right element should be greater than the current one.

Upvotes: 2

Mojtaba Khooryani
Mojtaba Khooryani

Reputation: 1875

use binary search and two-pointer technique. first sort the array, this function returns the index of least greater in O(log n) if exist otherwise returns -1

int LeasterGreater(int[] a, int value, int left, int right) {
    int low = left;
    int high = right;
    while (low != high) {
        int mid = (low + high) / 2;
        if (a[mid] <= value) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    if (low == right) {
        return -1;
    }
    return low;
}

example 1:

int[] arr = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
    Arrays.sort(arr);
    int leastGreaterIndex = LeasterGreater(arr, 58, 0, arr.length);
    if (leastGreaterIndex >= 0) {
        System.out.println(arr[leastGreaterIndex]);
    } else {
        System.out.println("doesn't exist!");
    }

output:

63

example 2:

int[] arr = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28};
    Arrays.sort(arr);
    int leastGreaterIndex = LeasterGreater(arr, 93, 0, arr.length);
    if (leastGreaterIndex >= 0) {
        System.out.println(arr[leastGreaterIndex]);
    } else {
        System.out.println("doesn't exist!");
    }

doesn't exist!

Upvotes: 2

RiaD
RiaD

Reputation: 47619

To solve it O(n log n) you may use TreeSet and go from right to left.

TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = ar.length - 1; i >= 0; --i) {
    set.higher(ar[i]); // what you need, may be null
    set.add(ar[i]);
}

Upvotes: 4

tgkprog
tgkprog

Reputation: 4598

Can use a temp variable of location of the current/ smallest value greater than the target and one loop. Boolean is optional, more clear. Can also use the temp var initialized to -1 & use as a flag in place of the boolean. Using one loop is faster for a bigger array and many calls. Full source 

        int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 };
        // Test cases
        ap.findLeasterGreater(arr, 0);
        ap.findLeasterGreater(arr, 1);
        ap.findLeasterGreater(arr, 11);
        ap.findLeasterGreater(arr, 6);
        // without boolean
        ap.findLeasterGreater2(arr, 0);
        ap.findLeasterGreater2(arr, 1);
        ap.findLeasterGreater2(arr, 11);
        ap.findLeasterGreater2(arr, 6);

    /*
     * One loop L-R, check if first greater val encountered. Ini currGreater, when a new value that > orig but < currGreater, use that as
     * the currGreater Using the location of curr greater so can return that. More useful.
     */
    int findLeasterGreater(int[] arr, int loc) {
        int nextGreaterLoc = -1;
        boolean first = true;
        for (int i = loc + 1; i < arr.length; i++) {
            if (first && arr[loc] < arr[i]) {
                first = false;
                nextGreaterLoc = i;
            } else if (arr[loc] < arr[i] && arr[nextGreaterLoc] > arr[i]) {
                nextGreaterLoc = i;
            }
        }
        if (nextGreaterLoc == -1) {
            System.out.println("Not found a value bigger than " + arr[loc] + " (after location " + loc + ")");
        } else {
            System.out.println("Found a value bigger :" + arr[nextGreaterLoc] + " at location " + nextGreaterLoc + " bigger than "
                    + arr[loc] + " (after location " + loc + ")");
        }
        return nextGreaterLoc;
    }

    /*
     * with 1 less local var - no boolean
     */
    int findLeasterGreater2(int[] arr, int loc) {
        int nextGreaterLoc = -1;
        for (int i = loc + 1; i < arr.length; i++) {
            if (nextGreaterLoc == -1 && arr[loc] < arr[i]) {
                nextGreaterLoc = i;
            } else if (nextGreaterLoc > -1 && arr[loc] < arr[i] && arr[nextGreaterLoc] > arr[i]) {
                nextGreaterLoc = i;
            }
        }
        if (nextGreaterLoc == -1) {
            System.out.println("Not found a value bigger than " + arr[loc] + " (after location " + loc + ")");
        } else {
            System.out.println("Found a value bigger :" + arr[nextGreaterLoc] + " at location " + nextGreaterLoc + " bigger than "
                    + arr[loc] + " (after location " + loc + ")");
        }
        return nextGreaterLoc;
    }
}

Upvotes: 0

maraca
maraca

Reputation: 8743

This is very easy solvable in O(n), just have to look if the number you are currently expecting is between the current solution and the number corresponding to the input, then you can update the solution:

public static int getNextIntToTheRight(int[] arr, int index) {
  int ret = Integer.MAX_VALUE; // initialize
  for (int i = index + 1; i < arr.length; i++) // for all items to the right of index
    if (arr[i] < ret && arr[i] > arr[index]) // if the inspected item is better
      ret = arr[i]; // update on the fly
  return ret; // this is now the solution, if there is any, otherwise Integer.MAX_VALUE
}

Upvotes: 0

Henry
Henry

Reputation: 43728

The second snippet is almost ok:

for (int i = 0; i < arr.length; i++) { // (1)
    int leastGreater = -1; // (2)
    for (int j = i + 1; j < arr.length; j++) {
        if ((arr[j] > arr[i])) {
            if(leastGreater == -1 || arr[j]<leastGreater){ // (3)
                leastGreater = arr[j];
            }
        }
    }
    arr[i] = leastGrater; // (4)
}
  1. We need to set the last element of the array as well, let the loop run over the whole array
  2. If nothing is found the value should be -1, so initialize to that
  3. need to replace also if nothing found yet
  4. set the new value into the array

Upvotes: 2

Related Questions