CareerCup

this can be done by dequeue with time complexity O(n)

public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
	        // write your code here
	     ArrayList<Integer> rst = new ArrayList<> ();
	     if (nums == null || nums.length == 0) {
	    	 return rst ;
	     }
	     LinkedList<Integer> q = new LinkedList<> ();
	     for (int i = 0 ; i < k ;++i) {
	        	while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
	        		q.pollLast() ;
	        	}
	        	q.offer(i) ;
	     }
	     int tail = 0 ;
	     for (int i = k ; i < nums.length ;++i) {
	    	 rst.add(nums[q.peek()]) ;
	    	 while (!q.isEmpty() && q.peek() <= tail) {
	    		 q.poll() ;
	    	 }
	    	 while (!q.isEmpty() && nums[i] > nums[q.peekLast()]) {
	    		 q.pollLast() ;
	    	 }
	    	 q.offer(i);
	    	 tail++;
	     }	  
	     rst.add(nums[q.peek()]) ;
	     return rst ;
	}

am i missing something? all of the above solutions O(k) space complexity. If K is small, then yes, it is ~ O(1). But then the solution is trivial.

You just need to keep an unsorted array of size K. Keep adding new numbers to it (loop around if array is full). Then you just go through all elements and find the max. that is an O(k) operation too

Ruby impl. Running time:O(n). Space: O(1).

# ascending order
@stream_iter=0
@stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
WIN_SIZE=3
@k_largest=@stream[0] if @stream.kind_of?(Array) && @stream.length >= 1

def has_more?
  @stream.kind_of?(Array) && @stream_iter < @stream.length
end

def max_int  
  return nil if WIN_SIZE <= 0
  return @k_largest if !has_more?
    
  if @k_largest.nil? || @stream[@stream_iter] > @k_largest
    @k_largest=@stream[@stream_iter]
  end
  
  @stream_iter+=1
  @k_largest
end

  
@stream.each do |value|
  puts "Max: #{max_int}"
end

puts "Max: #{max_int}"

Output:
Max: 1
Max: 4
Max: 4
Max: 7
Max: 9
Max: 15
Max: 15
Max: 26
Max: 96
Max: 96
Max: 96
Max: 96
Max: 96
Max: 96

. Use a balanced Binary tree to maintain k numbers in order
. Use a queue to maintain k numbers in sequence
Whenever a new number comes in,
1) remove the old one from the queue(O(1)) and search and remove it from the binary tree O(log k)
2) add the new number to the queue O(1) and add the new number to the binary tree O(log k)

For N numbers,
Time complexity: O(N log k) if k is considered a constant then O(N)
Space complexity: O(2K) if K is considered a constant then O(1)

Here's the correct Ruby impl. Running time: O(n)

require 'singleton'

class StreamSimulator
  include Singleton
  
  def initialize
    @stream_iter=0
    @stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
  end
  
  def has_more?
    @stream_iter < @stream.length
  end
  
  def fetch_next_int
    if has_more?
      @stream_iter+=1
      @stream[@stream_iter-1]
    end
  end
end

class SlidingWindow
  def initialize(win_size, stream)
    @win_size=win_size
    @stream=stream
    @buffer=Array.new(@win_size)
    @buffer_iter=0
    @current_iter=0
    @k_largest=nil
    @largest_position=nil
  end
  
  def end_of_window?
    @buffer_iter + 1 % win_size == 0
  end

  def largest_int
    @k_largest
  end

  def set_largest_int
    if largest_int.nil? || current_value > largest_int
      @k_largest=current_value
      @largest_position=@current_iter
    end
  end
  
  def win_size
    @win_size
  end
  
  # rotating buffer
  def fetch_next_int 
    @buffer[@buffer_iter]=@stream.fetch_next_int
    @current_iter=@buffer_iter
    @buffer_iter=@buffer_iter+=1 % win_size
    
     # if window has slided and largest int was not the last input read in the prev window
    if @buffer_iter==0 && @largest_position != win_size-1
      @largest_position=nil 
      @k_largest=nil 
    end
  end
  
  def current_value
    @buffer[@current_iter]
  end
  
  def find_max_int  
    return nil if win_size <= 0
    return largest_int if !@stream.has_more?
   
    fetch_next_int
    set_largest_int
    largest_int
  end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
  puts "Max int: #{sliding_win.find_max_int}"
end

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 15
Max int: 26
Max int: 96
Max int: 96
Max int: 96
Max int: 96
Max int: 96

Corrected Ruby impl...

require 'singleton'

class StreamSimulator
  include Singleton
  
  def initialize
    @stream_iter=0
    @stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
  end
  
  def has_more?
    @stream_iter < @stream.length
  end
  
  def fetch_next_int
    if has_more?
      @stream_iter+=1
      @stream[@stream_iter-1]
    end
  end
end

class SlidingWindow
  def initialize(win_size, stream)
    @win_size=win_size
    @stream=stream
    @buffer=Array.new(@win_size)
    @buffer_iter=0
    @current_iter=0
    @k_largest=nil
    @largest_position=nil
  end
  
  def end_of_window?
    @buffer_iter + 1 % win_size == 0
  end

  def largest_int
    @k_largest
  end

  def set_largest_int
    if largest_int.nil? || current_value > largest_int
      @k_largest=current_value
      @largest_position=@current_iter
    end
  end
  
  def win_size
    @win_size
  end
  
  # rotating buffer
  def fetch_next_int 
     # if window has slided and largest int was not the last input read in the prev window
    if @buffer_iter==0 && @largest_position != 1
      @largest_position=nil 
      @k_largest=nil 
    end
    
    @buffer[@buffer_iter]=@stream.fetch_next_int
    @current_iter=@buffer_iter
    @buffer_iter=(@buffer_iter+=1) % win_size
  end
  
  def current_value
    @buffer[@current_iter]
  end
  
  def find_max_int  
    return nil if win_size <= 0
    return largest_int if !@stream.has_more?
   
    fetch_next_int
    set_largest_int
    largest_int
  end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
  puts "Max int: #{sliding_win.find_max_int}"
end

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 11
Max int: 26
Max int: 96
Max int: 15
Max int: 15
Max int: 56
Max int: 25

Modified Ruby impl to use queue and hashet. Running time: O(n). Space: O(k).

require 'singleton'
require 'thread'
require 'set'

class StreamSimulator
  include Singleton
  
  def initialize
    @stream_iter=0
    @stream=[1,4,2,7,9,15,11,26,96,15,3,56,25]
  end
  
  def has_more?
    @stream_iter < @stream.length
  end
  
  def fetch_next_int
    if has_more?
      @stream_iter+=1
      @stream[@stream_iter-1]
    end
  end
end

class SlidingWindow
  def initialize(win_size, stream)
    @win_size=win_size
    @stream=stream
    @k_largest=nil
    @largest_position=0
    @window=SizedQueue.new(@win_size)
    @window_lookup=Set.new
  end

  def largest_int
    @k_largest
  end
  
  def within_window?(value)
    @window_lookup.include?(value)
  end

  def set_largest_int
    @k_largest=nil if !within_window?(@k_largest)
    @k_largest=current_value if @k_largest.nil? || current_value > @k_largest
  end
  
  def win_size
    @win_size
  end

  def fetch_next_int
    if @window.size == win_size
      @window_lookup.delete(@window.pop)
    end
     
    @input=@stream.fetch_next_int
    @window.push(@input)
    @window_lookup.add(@input)
    @input
  end
  
  def current_value
    @input
  end
  
  def find_max_int  
    return nil if win_size <= 0
    return largest_int if !@stream.has_more?
   
    fetch_next_int
    set_largest_int
    largest_int
  end
end

sliding_win=SlidingWindow.new(3,StreamSimulator.instance)

while StreamSimulator.instance.has_more?
  puts "Max int: #{sliding_win.find_max_int}"
end

Output:
Max int: 1
Max int: 4
Max int: 4
Max int: 7
Max int: 9
Max int: 15
Max int: 15
Max int: 26
Max int: 96
Max int: 96
Max int: 96
Max int: 56
Max int: 56

The solution for the problem in Javascript. Looking forward for feedback.

var windowMax = 0;
var maxFor = 0;
var findMaxInWindow = function (windowSize, value) {
  // console.log ("Finding the max in the range with the value" , value);
 
  if (value > windowMax) {
     windowMax = value;
     maxFor = 1;
  } else {
     maxFor ++;
  } 
  
  if (maxFor > windowSize) {
     windowMax = value;
     maxFor = 1;
  }
   
}


var main = function ( ){
   var windowSize = 3;
  
   var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 15, 3, 56, 25];
   var numOfValues = stream.length;
   for (var i = 0 ; i < numOfValues; i++) {
     var num = stream[i];
     //console.log (num);
     findMaxInWindow (windowSize, num);
     //console.log ("The window max is " + windowMax + " maxFor  " + maxFor);
      console.log (i + " ) " + stream[i] +" -  MAX : " + windowMax);
   }
}

main();

The output is :

0 ) 1 -  MAX : 1
1 ) 4 -  MAX : 4
2 ) 2 -  MAX : 4
3 ) 7 -  MAX : 7
4 ) 9 -  MAX : 9
5 ) 15 -  MAX : 15
6 ) 11 -  MAX : 15
7 ) 26 -  MAX : 26
8 ) 96 -  MAX : 96
9 ) 15 -  MAX : 96
10 ) 3 -  MAX : 96
11 ) 56 -  MAX : 56
12 ) 25 -  MAX : 56

My solution to the problem in Javascript.

var windowMax = 0;
var maxFor = 0;
var findMaxInWindow = function (windowSize, value) {
  // console.log ("Finding the max in the range with the value" , value);
 
  if (value > windowMax) {
     windowMax = value;
     maxFor = 1;
  } else {
     maxFor ++;
  } 
  
  if (maxFor > windowSize) {
     windowMax = value;
     maxFor = 1;
  }
   
}


var main = function ( ){
   var windowSize = 3;
  
   var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 15, 3, 56, 25];
   var numOfValues = stream.length;
   for (var i = 0 ; i < numOfValues; i++) {
     var num = stream[i];
     //console.log (num);
     findMaxInWindow (windowSize, num);
     //console.log ("The window max is " + windowMax + " maxFor  " + maxFor);
      console.log (i + " ) " + stream[i] +" -  MAX : " + windowMax);
   }
}

main();

The output

0 ) 1 -  MAX : 1
1 ) 4 -  MAX : 4
2 ) 2 -  MAX : 4
3 ) 7 -  MAX : 7
4 ) 9 -  MAX : 9
5 ) 15 -  MAX : 15
6 ) 11 -  MAX : 15
7 ) 26 -  MAX : 26
8 ) 96 -  MAX : 96
9 ) 15 -  MAX : 96
10 ) 3 -  MAX : 96
11 ) 56 -  MAX : 56
12 ) 25 -  MAX : 56

This is my solution for Java.
Notice you have to use TreeMap and not TreeSet in case you get reoccurring values

import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

public class MaxK {

	private TreeMap<Integer, Integer> tree;
	private Queue<Integer> queue;
	private final int k;

	public MaxK(int k) {
		if (k <= 0) {
			throw new IndexOutOfBoundsException();
		}
		tree = new TreeMap<Integer, Integer>();
		queue = new LinkedList<Integer>();
		this.k = k;
	}

	public int getMaxK(int num) {
		if (queue.size() >= k) {
			Integer lastNum = queue.poll();
			int refCount = tree.get(lastNum);
			if (refCount <= 0) {
				tree.remove(lastNum);
			} else {
				tree.put(lastNum, refCount - 1);
			}

		}

		queue.add(num);
		if (tree.containsKey(num)) {
			tree.put(num, tree.get(num) + 1);
		} else {
			tree.put(num, 0);
		}

		int maxK = tree.lastKey();
		return maxK;
	}
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

public class MaxK {

	private TreeMap<Integer, Integer> tree;
	private Queue<Integer> queue;
	private final int k;

	public MaxK(int k) {
		if (k <= 0) {
			throw new IndexOutOfBoundsException();
		}
		tree = new TreeMap<Integer, Integer>();
		queue = new LinkedList<Integer>();
		this.k = k;
	}

	public int getMaxK(int num) {
		if (queue.size() >= k) {
			Integer lastNum = queue.poll();
			int refCount = tree.get(lastNum);
			if (refCount <= 0) {
				tree.remove(lastNum);
			} else {
				tree.put(lastNum, refCount - 1);
			}

		}

		queue.add(num);
		if (tree.containsKey(num)) {
			tree.put(num, tree.get(num) + 1);
		} else {
			tree.put(num, 0);
		}

		int maxK = tree.lastKey();
		return maxK;
	}
}

My solution to the problem in C++.

#include <iostream>
#include <queue>
#include <set>

using namespace std;

class MaxInWindow {
private:
	queue<int> orderByInput;
	multiset<int> orderByValue;
public:
	int findMaxInWindow(int windowSize, int value) {
		orderByInput.push(value);
		orderByValue.insert(value);

		if (orderByInput.size() > windowSize) {
			orderByValue.erase( orderByInput.front() );
			orderByInput.pop();
		}

		return *orderByValue.rbegin();
	}
};

int main(int argc, char* argv[]) {
	MaxInWindow mw;
	int arr[] = {1, 4, 2, 7, 9, 15, 11, 26, 96, 56, 3, 15, 25};
	int i;

	for (i = 0; i < 13; i++) {
		cout << mw.findMaxInWindow(3, arr[i]) << "\n";
	}

	return 0;
}

Result

1
4
4
7
9
15
15
26
96
96
96
56
25

I changed test case.
[..., 15, 3, 56, ...] -> [..., 56, 3, 15, ...]

My solution to the problem in JavaScript.

var orderByInput = [];
var orderByValue = [];

var findMaxInWindow = function (windowSize, value) {
  var maxInWindow = orderByValue[0] || value;
  
  orderByInput.push(value);
  if (maxInWindow > value) {
    orderByValue.push(value);
  } else {
    orderByValue.splice(0, 0, value);
    maxInWindow = value;
  }

  if (orderByInput.length > windowSize) {
    var removeIndex = orderByValue.indexOf( orderByInput.shift() );
    orderByValue.splice(removeIndex, 1);
    if (removeIndex == 0) {
        orderByValue.sort(function(a, b){return b - a});
        maxInWindow = orderByValue[0];
    }
  }
  
  return maxInWindow;
}


var main = function ( ){
  var windowSize = 3;
  var stream = [1, 4, 2, 7, 9, 15, 11, 26, 96, 56, 3, 15, 25];

  for (var i = 0 ; i < stream.length; i++) {
    console.log (i + " ) " + stream[i] +" -  MAX : " + findMaxInWindow(windowSize, stream[i]));
  }
}

main();

Result:

0 ) 1 -  MAX : 1
1 ) 4 -  MAX : 4
2 ) 2 -  MAX : 4
3 ) 7 -  MAX : 7
4 ) 9 -  MAX : 9
5 ) 15 -  MAX : 15
6 ) 11 -  MAX : 15
7 ) 26 -  MAX : 26
8 ) 96 -  MAX : 96
9 ) 56 -  MAX : 96
10 ) 3 -  MAX : 96
11 ) 15 -  MAX : 56
12 ) 25 -  MAX : 25

If the runtime bigO/bigTheta is denoted with respect to both N and K, then the question seems to me to be impossible to satisfy.

imagine stream like this 0, -1 , -2 , -3, ... (keeps going down)

You cannot make both space O(1) and getMax operation O(1).

Here is my code:

class TS{
    int wsize;
    queue<int> window;
    deque<int> maxRec;

public:
    TS(int n): wsize(n){};

    int maxElem(int num){
        window.push(num);

        if (window.size()>wsize)
        {
           int victim= window.front();
           window.pop();
           if (victim==maxRec.front())
           maxRec.pop_front();
        }

        while(!maxRec.empty()&&num>maxRec.back())
        maxRec.pop_back();
    
        maxRec.push_back(num);

        return maxRec.front();
    }
};

#include<stdio.h>
int main()
{
int i=0,max=0;
while(i!=-999)
{
scanf("%d",&i);
if(i>max)
max=i;
}
printf("Max=%d",max);
}

#include <iostream>
#include <deque>
using namespace std;

struct stream{
        int key;
        int index;
};

int main(){

int k,key,n,i = 0;
stream s;
deque< stream > Q;
cin >> k >> key;

while ( i < k-1 && key != -1 ){
        while ( !Q.empty() && key >= Q.back().key )
                Q.pop_back();
        s.key = key;
        s.index = i++;
        Q.push_back( s );
        cin >> key ;
}

while ( key != -1 ) {
        cout<< Q.front().key<<"\n";
        cin >> key;
        while ( !Q.empty() && key >= Q.back().key )
                Q.pop_back();
        while ( !Q.empty() && ( Q.front().index <= i- k ) )
                Q.pop_front();
        s.key = key;
        s.index = i++;
        Q.push_back( s );
}

return 0;
}

This will work in O(N) time and O(k) space and it's taking input one by one .

C# solution.

class Program
    {
        static void Main(string[] args)
        {
LinkedLists ln = new LinkedLists();
            Console.WriteLine(ln.FindMaxinWindow(1,1));
            Console.WriteLine(ln.FindMaxinWindow(2, 2));
            Console.WriteLine(ln.FindMaxinWindow(-6, 1));
            Console.WriteLine(ln.FindMaxinWindow(33, 3));
            Console.WriteLine(ln.FindMaxinWindow(4, 8));
            Console.WriteLine(ln.FindMaxinWindow(9, 2));
            Console.WriteLine(ln.FindMaxinWindow(8, 2));
            Console.WriteLine(ln.FindMaxinWindow(99, 8));
            Console.WriteLine(ln.FindMaxinWindow(8, 2));
	    Console.Read();
}

}
public class LinkedLists
    {
        LinkedList<int> buffer = new LinkedList<int>();
        int bufferCount = 0;
        public int FindMaxinWindow(int input, int windowSize)
        {
            bufferCount++;
            buffer.AddFirst(input);
            if (windowSize <= 0)
                return 0;
            else if (windowSize > bufferCount)
                windowSize = bufferCount;
            int tempMax = input;
            foreach (var item in buffer)
            {
                if (windowSize > 0)
                {
                    if (item > tempMax)
                        tempMax = item;
                }
                windowSize--;
            }
            return tempMax;
        }
    }

create a max heap of size k - O(n) space
insert would be O(logn) time
return max from heap- O(1)

public class MaxWithinARangeFinder {
	private static int k;
	private static int[] arr = new int[100];
	private static int maxIdx = 1, currIdx;
	
	private static int doFind(int i) {
		arr[currIdx] = i; // {10, 9, 52, 13, 53} 2
		if(k == 1) return arr[currIdx]; 
		maxIdx = calculateMax(currIdx);
		++currIdx;
		return maxIdx;
	}

	private static int calculateMax(int currIdx) {
		// 1. check if current max is -1, if so - assign the first element and return
		int maxIdxLocal = maxIdx;
		if(maxIdx == -1) maxIdxLocal = 0;
		else {
			// check if prev max is within range
			if(currIdx - k < maxIdx) {
				// return max of prevMax and currIdx
				maxIdxLocal = max(maxIdx, currIdx);
			} else {
				// prev Max is gone out of the window size, calculate new max
				maxIdxLocal = calculateNewMax(currIdx);
			}
		}
		maxIdx = maxIdxLocal;
		return maxIdxLocal;
	}

	private static int max(int maxIdx, int currIdx) {
		return (arr[maxIdx] > arr[currIdx]) ? maxIdx : currIdx;
	}

	private static int calculateNewMax(int currIdx) {
		int cnt = k;
		int mIdx = currIdx;
		while(cnt > 0) {
			if(arr[currIdx] > arr[mIdx]) mIdx = currIdx;
			--currIdx;
			--cnt;
		}
		return mIdx;
	}
	
}

Hello. In order to solve this problem we can use a queue implemented on two stacks with additional operation getMax() defined both on queue and stack. In that case amortized query time will be O(1).