class KthLargest:
	
    #Big O: n 
    def __init__(self, k: int, nums: List[int]): 
        #minHeap with k largest integers 
        
        self.minHeap, self.k = nums, k 
        heapq.heapify(self.minHeap) 
        
        while len(self.minHeap) > k: 
            heapq.heappop(self.minHeap) 
            
        

    #Big O: log N 
    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val) 
        
        if len(self.minHeap) > self.k: 
            heapq.heappop(self.minHeap)
        
        return self.minHeap[0]
    

#Total big O: n log n 
    
    
    
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

class Solution:
    def binarySearch(self, nums, target):
        start, end = 0, len(nums) - 1 

        while start <= end: 
            middle = (start + end) // 2 
            current = nums[middle] 

            if target > current: 
                start = middle + 1 
            elif target < current: 
                end = middle - 1 
            else: 
                return middle
                #return current if you want value instead of index 
        return -1 
    
    
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0: 
            return -1 
        elif len(nums) == 1: 
            if nums[0] != target: 
                return -1 
            else: 
                return 0 
        else: 
            rotated = False
            lastIdx = len(nums) - 1 

            if nums[lastIdx] < nums[0]: 
                rotated = True 

            if rotated == False: 
                return self.binarySearch(nums, target) 
            else: 
                previous = nums[0]
                rotateIdx = 0 
                for i in range(1, len(nums)): 
                    if nums[i] < previous: 
                        rotateIdx = i 
                    previous = nums[i]
                    
                array1 = nums[:rotateIdx]
                array1Length = len(array1)
                array2 = nums[rotateIdx:] 

                if self.binarySearch(array1, target) == -1 and self.binarySearch(array2, target) != -1: 
                    return array1Length + self.binarySearch(array2, target)
                return self.binarySearch(array1, target)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
/*
var twoSum = function(nums, target) {
    var targetMap = new Map();
    var result = new Array();
    for(var i = 0; i < nums.length; i++)
        {
            var diff = target - nums[i];
            if(!targetMap.has(diff)){
                targetMap.set(nums[i],i);
            }else{
                result[0] = targetMap.get(diff);
                result[1] = i;
                return result;
            }
        }
    return result;
};
*/
const twoSum = function(nums, target) {
    const comp = {};
    for(let i=0; i<nums.length; i++){
        if(comp[nums[i] ]>=0){
            return [ comp[nums[i] ] , i]
        }
        comp[target-nums[i]] = i
    }
};