leeway00 / codingtestpractice Goto Github PK

def minimumSwaps(arr):
    n = len(arr)
    arrpos = [*enumerate(arr)]
    arrpos.sort(key = lambda it : it[1])
    vis = {k : False for k in range(n)}
     
    ans = 0
    for i in range(n):
        if vis[i] or arrpos[i][0] == i:
            continue
        cycle_size = 0
        j = i # j finds local cycle starting from i
        while not vis[j]: # finding cycle
            vis[j] = True # mark True when j is included in the cycle
            j = arrpos[j][0] # update j to the next position in the cycle
            cycle_size += 1 # increment cycle size
        if cycle_size > 0:
            ans += (cycle_size - 1)
    return ans

minimumSwaps(a)

  def threeSum(self, nums: List[int]) -> List[List[int]]:
      result = []
      nums.sort()
      for i in range(len(nums)-2):
          if i>0 and nums[i] == nums[i-1]:
              continue
          left, right = i+1, len(nums)-1
          while left < right:
              summ = nums[i] + nums[left] +nums[right]
              if summ <0:
                  left +=1
              elif summ >0:
                  right -=1
              else:
                  result.append([nums[i], nums[left], nums[right]])
                  
                  while left < right and nums[left] == nums[left+1]:
                      left +=1
                  while left < right and nums[right]==nums[right-1]:
                      right -=1
                  left+=1
                  right -=1
      return result

    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for ind, char in enumerate(s):
            # In case of resetting
            if char in used and start <= used[char]:
                start = used[char]+1
            # if not reset, update max_length
            else:
                max_length = max(max_length, ind-start+1)
            # update recently used index of char
            used[char] = ind
        return max_length

    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        out = ''
        s = self.countAndSay(n-1)
        count = 0
        for i in range(len(s)):
            c = s[i]
            if i == 0 or c == s[i-1]:
                count += 1
            else:
                out += str(count) + s[i-1]
                count = 1
        out += str(count) + c
        return out

    def increasingTriplet(self, nums: List[int]) -> bool:

        fst, snd = sys.maxsize, sys.maxsize        
        for i in nums:
            if i >  fst:
                if i > snd:
                    return True
                else:
                    snd = i
            else:
                fst = i
        return False
                

    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        should_set_row = [False for _ in matrix]
        should_set_col = [False for _ in matrix[0]]
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    should_set_row[i] = True
                    should_set_col[j] = True
        
        for i, should_set in enumerate(should_set_row):
            if should_set:
                matrix[i] = [0 for _ in matrix[0]]
        
        for j, should_set in enumerate(should_set_col):
            if should_set:
                for i in range(len(matrix)):
                    matrix[i][j] = 0

def minimumBribes(q):
    # Write your code here
    bribes = 0
    for i, p in enumerate(q, 1):
        if p-i >2:
            print("Too chaotic")
            return
        for j in range(i, len(q)):
            if p > q[j]:
                bribes +=1
    print(bribes)

def arrayManipulation(n, queries):
    # Write your code here
    plus, minus, values = [*zip(*queries)]
    # plus, minus = deque(plus), deque(minus)
    plus = sorted([*zip(plus, values)], key = lambda x: x[0])
    minus = sorted([*zip(minus, values)], key = lambda x: x[0])
    n = len(plus)
    maximum = 0
    current = 0
    plus_ind = 0
    minus_ind = 0
    while minus_ind < n:
        if plus_ind < n and plus[min(plus_ind,n-1)][0] <= minus[minus_ind][0]:
            current += plus[plus_ind][1] # value added after plus[plus_ind]
            plus_ind +=1
        else: # value decreased after minus[minus_ind]
            current -= minus[minus_ind][1]
            minus_ind +=1
        maximum = max(current, maximum)
    return maximum

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = defaultdict(list)

        for s in strs:
            ans[''.join(sorted(s))].append(s)
        
        return [*ans.values()]