Leetcode Sorting Problem Collection (1)

  • 56.Merge Intervals
  • 253.Meeting Rooms II
  • 973.K Closest Points to Origin
  • 148.Sort List *
  • 88.Merge Sorted Array

56. Merge Intervals

Sort first, then merge. Pretty straight forward.

1
2
3
4
5
6
7
8
9
10
11
12
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    begin, end = intervals[0]
    res = []
    for cur_begin, cur_end in intervals[1:]:
        if cur_begin <= end:
            end = max(end, cur_end)
        else:
            res.append([begin, end])
            begin, end = cur_begin, cur_end
    res.append([begin, end])
    return res

253. Meeting Rooms II

I use hashmap to log current using rooms. free variable is for reducing times of sum(rooms.values())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    from collections import defaultdict
    intervals.sort()
    rooms = defaultdict(int)
    cnt, free = 0, 0  
    for start, end in intervals:
        for time in list(rooms.keys()):
            if start >= time[-1]:
                free += rooms[time]
                del rooms[time] 
        rooms[(start, end)] += 1
        if free > 0:
            free -= 1
        else:
            cnt += 1
    return cnt

973. K Closest Points to Origin

I feels like it is a hack… pretty straight forward though.

1
2
3
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
    points.sort(key = lambda p: p[0]**2 + p[1]**2)
    return points[:K]

148. Sort List

A nice one, bascially is a merge sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def sortList(self, head: ListNode) -> ListNode:
    def merge(l1, l2):
      dummy = ListNode()
      cur = dummy
      while l1 and l2:
        if l1.val < l2.val:
          cur.next = l1
          l1 = l1.next
          else:
            cur.next = l2
            l2 = l2.next
            cur = cur.next
            cur.next = l1 if l1 else l2
            return dummy.next

          if not head or not head.next:
            return head
          
          # use 2 pointers to divide into 2 lsits
          # slow is list 2
          p, slow, fast = None, head, head
          while fast and fast.next:
            p = slow
            slow = slow.next
            fast = fast.next.next
            p.next = None
            return merge(self.sortList(head), self.sortList(slow))

88. Merge Sorted Array

I don’t think it is an Easy at all.
My initial solution: maintain 2 pointers, current index of nums1, and nums2. If n1 > n2, need ro insert n2 before n1. which means swap all the following digit from n1 till the end of num1.
This solution is pretty slow. Time complexity is O(m^n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i1, i2 = 0, 0
    while i2 < n and i1 < m:
        if nums1[i1 + i2] > nums2[i2]:
            pre = nums2[i2]
            for i in range(i1 + i2, m + i2 + 1):
                temp = nums1[i]
                nums1[i] = pre
                pre = temp
            i2 += 1
        else:
            i1 += 1
    if i2 < n:
        nums1[i1 + i2: ] = nums2[i2:]

Assign descending can avoid swapping.
time: O(n+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i1 = m - 1
    i2 = n - 1
    for i in range(m + n - 1, -1, -1):
        if i1 < 0: 
            nums1[i] = nums2[i2]
            i2 -= 1
        elif i2 < 0:
            nums1[i] = nums1[i1]
            i1 -= 1
        elif nums2[i2] > nums1[i1]:
            nums1[i] = nums2[i2]
            i2 -= 1
        else:
            nums1[i] = nums1[i1]
            i1 -= 1