Leetcode Solutions 1.3

56. Merge Intervals

# Array #Sort

Similar to #763 Partition Labels

def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        # print(intervals)
        intervals = [[i.start, i.end] for i in intervals]
        intervals.sort()
        out = []
        current_index = 0 
        while(current_index < len(intervals)):
            return_val = [intervals[current_index][0], intervals[current_index][1]]
            # print(return_val, current_index)
            current_index += 1
            # print(current_index, len(intervals))
            while current_index < len(intervals) and intervals[current_index][0] <= return_val[1] and intervals[current_index][1] >= return_val[0]:
                return_val[1] = return_val[1] if return_val[1] > intervals[current_index][1] else intervals[current_index][1]
                return_val[0] = return_val[0] if return_val[0] < intervals[current_index][0] else intervals[current_index][0]
                current_index += 1
                
            out.append(return_val) 
            
        out.sort()            
        out = [Interval(i[0], i[1]) for i in out] 
        return out

495. Teemo Attacking

# Array # Complexity O(n)

def findPoisonedDuration(self, timeSeries, duration):
        """
        :type timeSeries: List[int]
        :type duration: int
        :rtype: int
        """
        poisoned_timings = []
        for time in timeSeries:
            if not poisoned_timings:
                poisoned_timings.append((time, time+duration))
            elif poisoned_timings[-1][1] >= time:
                start, end = poisoned_timings.pop()
                poisoned_timings.append((start, time + duration))
            else:
                poisoned_timings.append((time, time+duration))
            
        total_time = 0
        for t in poisoned_timings:
            total_time += t[1] - t[0]
            
        return total_time

649. Dota2 Senate

# Queue #Medium problem (Easy to confuse with mod iteration of array , it’s not)

# Complexity O(n)

def predictPartyVictory(self, senate: str) -> str:
        queue = collections.deque()
        people, bans = [0, 0], [0, 0]
        for person in people:
            x = person == "R"
            people[x] += 1
            queue.append(x)
            
        while all(people):
            x = queue.popleft()
            if bans[x]:
                bans[x] -= 1
                people[x] -= 1
            else:
                bans[x^1] += 1
                queue.append(x)
        return "Radiant" if people[1] else "Dire"

961. N-Repeated Element in Size 2N Array

Code : Brute force hash table + count O(n)

class Solution(object):
    def repeatedNTimes(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        hash_table = {}
        for element in A:
            if not hash_table.get(element):
                hash_table[element] = 1
            else:
                hash_table[element] += 1
                
        for key, value in hash_table.items():
            if value == len(A) // 2:
                return key

977. Squares of a Sorted Array

Code : Linear traversal and sort or 2 pointers (one for negative and one for positive)

def sortedSquares(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        n = len(A)
        j = 0
        # i, j : negative and positive parts
        while(j < n and A[j] < 0):
            j += 1
        i = j - 1 
        
        ans = []
        while 0 <= i and j<n:
            if A[i]*A[i] <= A[j]*A[j]:
                ans.append(A[i]*A[i])
                i-=1
            else:
                ans.append(A[j]*A[j])
                j+=1
                
        while(i >= 0):
            ans.append(A[i]*A[i])
            i-=1
       
        while(j < n):
            ans.append(A[j] * A[j])
            j += 1
        return ans