Finding next occurance for each element in array in O(n)

Question

Suppose I have an array like this : [ 1, 2, 3, 4, 5, 6, 1]

I want to get an output like 1 ==> 6 ( For element 1(0^th index the match is found at index 6)

This means for 0^th element the next match is found at 6th index.

If the input is [4,6,4,6] the output is 4 ==> 2 and 6 ==> 3

Since first match for 4 is found at index 2( which is four) and first match for six(2^nd element) is found at 3^rd index

If the time complexity is O(n²) the solution is pretty straight forward. I have tried to find the next greatest element with this code in O(n) using stack. But I couldn't find a way to do the same for next equal element.

import java.util.Scanner;
import java.util.Stack;

public class NextGreatestElement {
    public static void main(String[] args) {
        int[] inp = {1,4,6,2,39};
        Stack<Integer> stack = new Stack<>();
        stack.push(inp[0]);
        for (int i = 1; i < inp.length; i++) {
            int element = inp[i];
            if (element > stack.peek()) {
                System.out.println(stack.peek() + " ==> " + element);
                stack.pop();
                while (!stack.isEmpty()) {
                    System.out.println(stack.pop() + " ==> " + element);
                }
                stack.push(element);
            } else if (element < stack.peek()) {
                stack.push(element);
            }
        }
        while (!stack.isEmpty()) System.out.println(stack.pop() + " ==> " + (-1));
    }
}

Even Algorithm is enough. I don't need the code.

Answer 1

It is not possible to implement it with a stack in O(n). You can take a HashMap and iterate from right to left saving the last occurrence of a number. It will give you O(n) average-case time complexity:

int[] inp = {1, 2, 3, 1, 2, 1, 3};
Map<Integer, Integer> h = new HashMap<>();
List<Integer> result = new ArrayList<>();

for (int i = inp.length - 1; i >= 0; --i) {
    int cur = inp[i];
    int next = -1;
    if (h.containsKey(cur)) {
        next = h.get(cur);
    }   
    h.put(cur, i);
    result.add(next);
}

for (int i = 0; i < inp.length; ++i) {
    System.out.println("Number " + inp[i] + " next occurence at index " + result.get(inp.length - i - 1));
}

Runnable version: http://ideone.com/i6Cx09

Answer 2

if i'm not mistaken if you want the element or get the element that occurs in array more than onece. You can do this.

This solution will be nlogn

1. Sort the array (ascending)
2. loop array then compare
3. if a[i] == a[i+1] then list.add(a[i]);

something like this enter image description here

Answer 3

Use a hashmap or hashtable

traverse from right to left, for the first occurrence input the value into the collection

collection_object.put(inp[i], ""+i)

when you encounter next time just change the value like

value = collection_object.get(inp[i])
v = value.split("==>")
value = v[0] + "==>" + i
collection_object.put(inp[i], value)