Untitled

mail@pastecode.io avatar
unknown
python
a year ago
865 B
2
Indexable
Never
class Solution:
    def countWays(self, nums: List[int]) -> int:
        hm=defaultdict(int)
        for n in nums:
            hm[n]+=1
        
        # sorting dictionary
        myKeys = list(hm.keys())
        myKeys.sort()
        sorted_dict = {i: hm[i] for i in myKeys}

        g=0
        k,v=list(sorted_dict.keys()),list(sorted_dict.values())
        n=len(k)
        
        if n==1:
            return v[0]
        
        # 2d map
        grid=[[-1]*n for _ in range(n)]
        
        for i in range(n):
            grid[i][i]=v[i]
            
        for i in range(n):
            for j in range(i+1,n):
                grid[i][j]=v[j]+grid[i][j-1]
        
        for i in range(n):
            for j in range(i,n):
                if grid[i][j]>k[j]:
                    g+=1
        return g