CareerCup

Try some cases brute force on paper, then when you try this case you get the idea
: 4 3 2 1 2 3 4
And it it clear from question itself that the alg. you should scan from right to left.
DS needed is a stack..

And also, as I'm coding I realize we should have sentinel value like INF (you can replace with whatever, maybe even replace with a[i] at that point) when no result exists (especially the rightmost answer):

call invocation of this stack, S:

for( i = N-1; i>=0; i-- )  
{
    while( !S.isEmpty && a[i] >= S.checkTop() )  //try to find > a[i] element
        S.pop();

    if( S.isEmpty ) 
        result[i]= INF;  //nothing > a[i] to right  (or use a[i] instead of INF) 
    else
        result[i]= S.checkTop();    //this was > a[i] to right
 
    S.push(a[i]);  
}

Find the bugs.
Please double test the code.
runtime O(n)
worstcase aux space O(n)

Well, we have

int input[n] = {7, 5, 6, 3, 4, 1, 2, 9, 11};

we want to get

int answer[n]; // = {9, 6, 9, 4, 9, 2, 9, 11, -1}
for(int i=0; i<n; ++i)
	answer[i] = -1;

I mark numbers that doesn't have bigger at right side as -1.
We can replace -1 with anything we need later.

We will save all positions, for which we still didn't find answers in stack.
At the start, stack is empty.

stack<int> still_without_answer;

Now, we are going to iterate throw the array.

for(int i=0; i<n; ++i)

For each number, we will find all numbers on the left sife, that less then current.
We will delete them from the stack.
So after that, all numbers in the stack will be bigger then current.
That mean that our stack is decreasing order and we can check only the top value, instead of iteration throw stack.

int smallest_without_answer = still_without_answer.top();
while(!still_without_answer.empty()&&input[smallest_without_answer]<input[i])
{
	answer[smallest_without_answer ] = input[i];
	still_without_answer.pop();
}
int smallest_number_without_answer = still_without_answer.top();

After setting current number as answer for smaller numbers, we push them to stack. Now it is the smallest number without answer.

still_without_answer.push(i);

This is O(n), becouse we iterate 1 time throw each elements, 1 time put each element to the stack for O(1), and 1 time delete from the stack for O(1).

Complete example in C++11. Should be O(n):

#include <iostream>
#include <vector>
#include <iterator>
#include <sstream>
#include <algorithm>


void findMax(std::vector<int> &v, unsigned int& idx)
{
	unsigned int currIdx = idx++;
	
	do {
		if (idx == v.size()) return;
		if (v[currIdx] < v[idx]) {
			v[currIdx] = v[idx];
			return;
		}
		findMax(v, idx);
	} while (true);
}

void SetNearestMax(std::vector<int> &v)
{
	unsigned int idx = 0;
	while (idx < v.size() - 1)
	{
		findMax(v, idx);
	}
}


int main()
{
	std::vector<int> v = {7, 5, 6, 3, 4, 1, 2, 9, 11};
 
	std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;
    SetNearestMax(v);
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;

    return 0;
}

nested for loops make o(n^n) and for loop + for loop make o(n) right/?
for()
{
for()
{
}
}
above is o(n^n)


but

for()
{

}
for()
{
}
the above code gives o(n)

public class Sample {
public static void main(String[] args) {
int[] a = {7,5,6,3,4,1,2,9,11};
for (int i = 0; i < a.length-1; i++) {
if(a[i]>a[i+1])
{
int p = i,q =i + 1;
while(true)
{
q++;
if(a[p]<a[q])
{
a[p] = a[q];
break;
}
}
}
else
a[i] = a[i+1];
}
for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

}


}

public class Sample {
public static void main(String[] args) {
int[] a = {7,5,6,3,4,1,2,9,11};
for (int i = 0; i < a.length-1; i++) {
if(a[i]>a[i+1])
{
int p = i,q =i + 1;
while(true)
{
q++;
if(a[p]<a[q])
{
a[p] = a[q];
break;
}
}
}
else
a[i] = a[i+1];
}
for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

}


}

void ReplaceWithMax2Right(int *a)
{
 if(a==NULL)
   return;
int n=sizeof(a)/sizeof(a[0]);
int max=a[n-1];
for(int i=n-2;i>=0;i--)
{
  int tmp=a[i];
 a[i]=max;
 if(max<tmp)
   max=tmp;
}
}

static void greNext(int []A){
		int l=A.length;
		int j=1;
		Stack eleA=new Stack();
		Stack index=new Stack();
		
		eleA.push(A[0]);
		index.push(0);
		
		while(j<l){
			while(!eleA.isEmpty() && A[j]>eleA.getTop()){
				A[index.pop()]=A[j];
				eleA.pop();
			}
			
			eleA.push(A[j]);
			index.push(j);
			j++;
		}
		
		if(j==l){
			while(!index.isEmpty()){
				A[index.pop()]=eleA.pop();
			}
		}
		
		for(int a:A){
			System.out.print(a+" ");
		}
	}

I do not think this problem can be solved in O(n) time. The best I can think of is O(n*log(n)*log(n))

I am wondered nobody thought of this, try solving problem from right end, you can do it in O(n).

if i give the input as 7,5,6,15,4,1,2,9,11 then the output should be 15,6,15,15,9,11,11 i guess. but iam getting 15,6,15,INF,9,2,9,11,15.
please correct me if iam wrong.

can't we use the below code, iam not sure about the complexity,
for(int i=0;i<a.length-1;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[j]>a[i])
{
a[i]=a[j];
break;
}
}
}

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package interview;

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

/**
 *
 * @author
 */
public class NextBigNumber {
    private int array[];
    
    private Stack<Integer> stack;
    public NextBigNumber()
    {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        array = new int[n];
        for(int i = 0;i<n;i++)
            array[i] = sc.nextInt();
        stack = new Stack<Integer>();
    }
    
    public void arrange()
    {
        stack.push(array[array.length-1]);
        for(int i=array.length-2;i>=0;i--)
        {
            int current = array[i];
            if(current<=stack.peek())
            {
                array[i]=stack.peek();
                stack.push(current);
            }
            else
            {
                while(!stack.empty() && current > stack.peek())
                {
                    stack.pop();
                    
                }
                if(!stack.empty())
                {
                    array[i]=stack.peek();
                    
                }
                stack.push(current);
            }
        }
    }
    
    public void print()
    {
        for(int i = 0;i<array.length;i++)
        {
            System.out.print(array[i]+" ");
        }
    }
    
    
}

just another solution:

public class Replace {

	Stack<Integer> store = new Stack<Integer>();
	int[] input;
	
	public int[] replace(int[] inputArr){
		input = inputArr;
		replaceHelper(input[input.length-1], input.length-2);
		return input;
	}
	
	private void replaceHelper(int curr_max, int index){
		System.out.println("index: "+index);
		System.out.println("curr_max: "+curr_max);
		if(index<0) return;
		if(curr_max>input[index]){
			int next_max=input[index];
			input[index] = curr_max;
			store.push(curr_max);
			//curr_max = input[index];
			System.out.println("next_max: "+next_max);
			System.out.println("--------------------");
			replaceHelper(next_max,--index);
		}
		else if(!store.isEmpty()){
			int prev_max = store.pop();
			System.out.println("prev_max: "+prev_max);
			System.out.println("--------------------");
			replaceHelper(prev_max,index);
		}
	}
	
	public static void main(String[] args){
		Replace rep = new Replace();
		int[] inputArr = {7,5,6,3,4,1,2,9,11};
		System.out.println("replaced array is: "+Arrays.toString(rep.replace(inputArr)));
		
	}
	
}

public class ReplaceNearestBiggestNumberArray {

public static void main(String args[]){
int[] origianlArr = {7, 5, 6, 3, 4, 1, 2, 9, 11};
ReplaceNearestBiggestNumberArray in = new ReplaceNearestBiggestNumberArray();
for(int i=0;i<origianlArr.length-1;i++){
origianlArr[i]= in.getNearestBiggestNumArray(origianlArr,i+1,origianlArr[i]);
}
for(int j=0;j<origianlArr.length;j++){
System.out.print(origianlArr[j]+" ");
}
}

public int getNearestBiggestNumArray(int[] arr, int start, int num){
for(int i=start;i<arr.length;i++){
if(num < arr[i]){
return arr[i];
}
}
return 0;
}
}

private static void printArrayWithFirstRightMaximum(int[] a) {
		int i = 0;
		int j = i+1;
		while(i<a.length && j<a.length) {
			if(a[i] < a[j]) {
				a[i] = a[j];
				i++;
				j=i+1;
			} else {
				if(j == a.length-1) {
					i++;
					j=i+1;
				}
				j++;
			}
		}
		printArray(a);

}

public class LargestRightsideNumber {

public static void main(String[] args) {


int[] arr ={7, 5, 6, 3, 4, 1, 2, 9, 11 };
for(int i=0; i<arr.length-1;i++){

int j=i;
while(arr[i] > arr[j+1]){
j++;
}

arr[i]=arr[j+1];

}

for(int i :arr){
System.out.print(i +" ");
}

}

}

#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int a[]={7,5,6,3,4,1,2,9,11};
int n=sizeof(a)/sizeof(a[0]);
cout<<n<<endl;
vector<int>ans;
ans.push_back(a[n-1]);
stack<int>s;
for(int i=n-2;i>=0;i--)
{
if(a[i]<a[i+1])
{
ans.push_back(a[i+1]);
s.push(a[i+1]);
}
else
{
while(s.top()<=a[i])
{
s.pop();
}

ans.push_back(s.top());
s.push(a[i]);
}
}
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";


return 0;
}

public static ArrayList<Integer> rightsideNearestMaximum(int[] nums){
		ArrayList<Integer> result = new ArrayList<>();
		
		int len = nums.length; 
		
		Deque<Integer> q = new ArrayDeque<>();
		q.offer(len-1); 
		result.add(nums[len-1]);
		for ( int i = len-2; i>= 0; i--) {
			while(!q.isEmpty() && nums[i] > nums[q.peekLast()] ) {
				q.pollLast();
			}
			if ( q.isEmpty()) {
				result.add(0, nums[i]);
			}else {
				result.add(0, nums[q.peekLast()]);
				q.add(i);
			}
		}
		return result; 
	}

public class EatenLives{
    public static void main(String[] args)
    {
    	boolean flag = false;
    	int input[] = {7, 5, 6, 3, 4, 1, 2, 9, 11};
    	for(int i = 0; i<input.length - 1; i++)
    	{
    		for(int j = i+1; j<input.length; j++)
    		{
    			if(input[i] < input[j] && flag != true)
    			{
    				input[i] = input[j];
    				flag = true;
    			}
    		}
    		flag = false;
    	}
    	for(int ip : input) 
    	{
    	    System.out.println(ip);
    	}
    }
}

public class EatenLives{
    public static void main(String[] args)
    {
    	boolean flag = false;
    	int input[] = {7, 5, 6, 3, 4, 1, 2, 9, 11};
    	for(int i = 0; i<input.length - 1; i++)
    	{
    		for(int j = i+1; j<input.length; j++)
    		{
    			if(input[i] < input[j] && flag != true)
    			{
    				input[i] = input[j];
    				flag = true;
    			}
    		}
    		flag = false;
    	}
    	for(int ip : input) 
    	{
    	    System.out.println(ip);
    	}
    }
}

public static void main(String[] args) {
int[] arr = {7, 5, 6, 3, 4, 1, 2, 9, 11};
ArrayOperations arrayOperations = new ArrayOperations();
int[] res = arrayOperations.replaceElementsWithNextGreat(arr);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + " ");
}
}


/**
* <p>Replace element of an Array with nearest bigger number at right side of the Array in O(n)
* <br>For example if the input Array is
* <br>7, 5, 6, 3, 4, 1, 2, 9, 11
* <br>output array should be
* <br>9, 6, 9, 4, 9, 2, 9, 11, 11</p>
*
* @param arr
* @return
*/
public int[] replaceElementsWithNextGreat(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Stack<Integer> st = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && arr[i] >= st.peek()) //try to find > a[i] element
st.pop();
if (st.isEmpty())
result[i] = arr[i]; //nothing > a[i] to right (or use a[i] instead of INF)
else
result[i] = st.peek(); //this was > a[i] to right
st.push(arr[i]);
}
return result;
}

public class Sample {
public static void main(String[] args) {
int[] a = {7,5,6,3,4,1,2,9,11};
for (int i = 0; i < a.length-1; i++) {
if(a[i]>a[i+1])
{
int p = i,q =i + 1;
while(true)
{
q++;
if(a[p]<a[q])
{
a[p] = a[q];
break;
}
}
}
else
a[i] = a[i+1];
}
for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + " ");

}

}


}

Please correct me if I am wrong

/**
* time: O(N)
* space: O(N)
*/
void replaceWithBiggestFromRight( int[] arr ){

Deque<Integer> biggestRight = new ArrayDeque<>();

for( int i = arr.length-1; i >=0; i-- ){

int temp = arr[i];

while( ! biggestRight.isEmpty() && biggestRight.peekFirst() <= arr[i] ){
biggestRight.pop();
}

if( ! biggestRight.isEmpty() ){
arr[i] = biggestRight.peekFirst();
}

biggestRight.push( temp );
}
}

Heres a method i wrote in ruby. You use a stack, and you go through each element in the array once and push and pop an element once so it should all be O(n)

def replace(array)
stack = Array.new
stack.push(array[array.size-1])
(array.size-2).downto(0) do |i|
while array[i] > stack[stack.size-1] do
stack.pop
if stack.size == 0
break
end
end
stack.push(array[i])
array[i] = stack[stack.size-2]
end
return array
end

for(int i =0;i < n;i++){
	max = Array[i + 1];
	for(int j = i+2;j < n;j++){
		if(Array[j] > max){
			max = Array[j];
		}
	}
	Array[i] = max;
}

A small change:

for(int i =0;i < n;i++){
	
	for(int j = i+1;j < n;j++){
		if(Array[j] > Array[i]){
			Array[i] = Array[j];
			break;
		}
	}
}

#include<stdio.h> 
int main() 
{ 
	int a[] = {7, 5, 6, 3, 4, 1, 2, 9, 11};
	int temp [9];
	int i,j;
	for(i=0;i<sizeof(a)/sizeof(int);i++)
	{
		if(i == (sizeof(a)/sizeof(int)-1))
		{
			temp[i]=a[i];
			break;
		}

		for(j=i+1;j<sizeof(a)/sizeof(int);j++)
		{
			if(a[j]>a[i])
			{
              temp[i] = a[j];
			  break;
			}
		}
	}

	for(i=0;i<sizeof(a)/sizeof(int);i++)
		printf("%d ",temp[i]);
  return 0; 
}

I dont think these solutions are in order of n