Day1: (Arrays)

1. Find the duplicate in an array of N integers. Solved on: 15th July 2020

def findDuplicate(self, nums: List[int]) -> int:
    l=[]
    for item in nums:
        if item in l:
            return (item)
        else:
            l.append(item)

2. Sort an array of 0’s 1’s 2’s without using extra space or sorting algo Looked for answer: 15th July 2020

def sortColors(self, nums: List[int]) -> None:
    # Point at the last 0
    l=0
    r=len(nums)-1
    curr=0
    while (curr<=r):
        if (nums[curr]==0):
            nums[l], nums[curr] = nums[curr], nums[l]
            l=l+1
            curr=curr+1
        elif (nums[curr]==2):
            nums[curr], nums[r] = nums[r], nums[curr]
            r=r-1
        else:
            curr=curr+1
            

3. Repeat and Missing Number Looked for answer on: 15th July 2020

def missingNumber(self, nums: List[int]) -> int:
    x=0
    for i in range(len(nums)+1):
        if x in nums:
            x=x+1
        else:
            return (x)

4. Merge two sorted Arrays without extra space Looked for answer on 16th July 2020

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums = nums1[:m]
        i1=0
        i2=0
        for i in range(m+n):
            if i1 <= m-1 and i2 <= n-1:
                nums1[i] = min(nums[i1],nums2[i2])
                if nums[i1]<=nums2[i2]:
                    i1=i1+1
                else:
                    i2=i2+1
            elif i1 == m:
                nums1[i:] = nums2[i2:]
                break
            elif i2 == n:
                nums1[i:] = nums[i1:]
                break

5. Kadane’s Algorithm Looked for answer on: 16th July 2020

def maxSubArray(self, nums: List[int]) -> int:
    max_cur = max_glo = nums[0]
    for i in range(1, len(nums)):
        max_cur = max(nums[i], max_cur + nums[i])
        if max_cur > max_glo:
            max_glo = max_cur
    return max_glo

6. Merge Overlapping Sub intervals Looked for answer on: 16th July 2020

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort(key=lambda x:x[0])
    i=1
    while (i<len(intervals)):
        if ( intervals[i][0] <= intervals[i-1][1] ):
            intervals[i-1][0] = min(intervals[i-1][0], intervals[i][0])
            intervals[i-1][1] = max(intervals[i-1][1], intervals[i][1])
            intervals.pop(i)
        else:
            i=i+1
    return (intervals)