Interesting Queries

interestingQuery.py

#User function Template for python3
import math
class Solution:
	def solveQueries(self, nums, Queries, k):
        
        
        
        originalLocation = Solution.saveQueryLocation(Queries)
        Queries = Solution.sortQ(Queries,len(nums),nums)
        
        #declare vars
        totalAns = []
        count = {}
        currentL = Queries[0][0]-1
        currentR = Queries[0][0]-1
        ans = 0
        
        for i in range(len(Queries)):
            
            while(currentL > Queries[i][0]-1):
                if nums[currentL] in count :
                    count.update(
                        {
                            nums[currentL]: count[nums[currentL]]+1
                        })
                        
                else:
                    count[nums[currentL]] = 1
                
                if  count[nums[currentL]] == k:
                    ans+=1
                    
                currentL -= 1
                
            while(currentR < Queries[i][1]):
                if nums[currentR] in count :
                    count.update(
                        {nums[currentR]: count[nums[currentR]]+1
                            
                        })
                        
                else:
                    count[nums[currentR]] = 1
                
                if count[nums[currentR]] == k:
                    ans+=1
                    
                currentR +=1
                
            while(currentL < Queries[i][0]-1):
                if nums[currentL] in count :
                    if(count[nums[currentL]]!=0):
                        val = count[nums[currentL]]-1
                        
                        count.update({
                            nums[currentL]: val
                            
                        })
                        
                    if count[nums[currentL]] == k-1:
                        ans-=1
                        
                currentL +=1
                
            while(currentR > Queries[i][1]):
                if nums[currentR-1] in count :
                    if(count[nums[currentR-1]]!=0):
                        val = count[nums[currentR-1]]-1
                        count.update({
                            nums[currentR-1]: val
                        })
                        
                    if count[nums[currentR-1]] == k-1:
                        ans-=1
                        
                currentR -=1
                
            totalAns.append(ans)
        
        newLocation = Solution.getQueryLocation(Queries,originalLocation,totalAns)
        
        retAns = [0] * len(totalAns)    
     
        for key,val in newLocation.items():
            
            if type(newLocation[key]) ==int:
                
                retAns[originalLocation[key]] = val
                
            else:
                for i in range(len(newLocation[key])):
                    
                    retAns[originalLocation[key][i]] = val[i]
        
        return retAns
        
    
    
    
    def sortQ(Queries,n,arr):
        
        B = math.ceil(math.sqrt(n))
        
        blocks = math.ceil(n/B)
        newQ = []
        
        groups = []
        for i in range(blocks):
            groups.append([])
            
        for j in range(len(Queries)):
            group = int(math.ceil(Queries[j][0]/B))
            groups[group-1].append(Queries[j])
            
        for i in range(len(groups)):
            group = sorted(groups[i], key = lambda x:x[0])
            for j in range(len(group)):
                newQ.append(group[j])
                
        for i in range(1,len(newQ)):
            if newQ[i][0] == newQ[i-1][0]:
                if newQ[i][1] < newQ[i-1][1]:
                    newQ[i], newQ[i-1] = newQ[i-1],newQ[i]
        return newQ
    
    def saveQueryLocation(Queries):
        
        originalLocation = {}
        
        for i in range(len(Queries)):
            
            key = str(Queries[i][0])+str(Queries[i][1])
            
            if key in originalLocation.keys() and type(originalLocation[key]) == int :
                
                originalLocation.update({key: [originalLocation[key],i]})
                
            elif key in originalLocation.keys() and type(originalLocation[key]) != int:
                
                arr = originalLocation[key]
                arr.append(i)
                originalLocation.update({key: arr})
                
            else:
                
                originalLocation[key] = i
                
        return originalLocation
        
    def getQueryLocation(Queries,originalLocation,totalAns):
        
        newLocation = {}
        
        for i in range(len(Queries)):
            
            key = str(Queries[i][0])+str(Queries[i][1])
            
            if key in newLocation.keys() and type(newLocation[key]) == int :
                
                newLocation.update({
                    key: [newLocation[key],totalAns[i]]
                })
                
            elif key in newLocation.keys() and type(originalLocation[key]) != int:
                
                arr = newLocation[key]
                arr.append(totalAns[i])
                newLocation.update({
                    key: arr
                })
                
            else:
                newLocation[key] = totalAns[i]
                
        return newLocation