leetcode

Search a 2D Matrix II

Search a 2D Matrix II

zip Version - 52ms

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for line in zip(*matrix):
            if target in line:
                return True
        return False

Another Version - 48ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix: return False
        m, n = len(matrix), len(matrix[0])
        row, col = 0, n - 1
        while row < m and col >= 0:
            if matrix[row][col] == target:
                return True
            if matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        return False

test code

1
2
3
4
5
6
7
8
9
In [27]: s = Solution(); t = s.searchMatrix(m, 20)
In [28]: t
Out[28]: False
In [29]: s = Solution(); t = s.searchMatrix(m, 5)
In [30]: t
Out[30]: True

leet code

leetcode

Container With Most Water

Container With Most Water

One Version - 96ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        i, j = 0, len(height) - 1
        left = right = water = 0
        while i <= j:
            left, right = max(left, height[i]), max(right, height[j])
            while i <= j and height[i] <= left <= right:
                water = max(water, (j - i) * min(left, right))
                i += 1
            while i <= j and height[j] <= right <= left:
                water = max(water, (j - i) * min(left, right))
                j -= 1
        return water

Another Version - 72ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        i, j = 0, len(height) - 1
        water = 0
        while i <= j:
            water = max(water, (j - i) * min(height[i], height[j]))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return water

test code

1
2
3
4
In [7]: s = Solution(); t = s.maxArea([1,8,6,2,5,4,8,3,7])
In [8]: t
Out[8]: 49

leet code

leetcode

Longest Consecutive Sequence

Longest Consecutive Sequence

O(n) Version - 40ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """    
        nums = set(nums)
        maxlen = 0
        while nums:
            first = last = nums.pop()
            while first - 1 in nums:
                first -= 1
                nums.remove(first)
            while last + 1 in nums:
                last += 1
                nums.remove(last)
            maxlen = max(maxlen, last - first + 1)
        return maxlen

O(n) Version - 44ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        ret = 0
        for x in nums:
            if x - 1 not in nums:
                y = x + 1
                while y in nums:
                    y += 1
                ret = max(ret, y - x)
        return ret

test code

1
2
3
4
In [66]: s = Solution(); t = s.longestConsecutive([100, 4, 200, 3, 1, 2])
In [67]: t
Out[67]: 4

leet code

leetcode

Trapping Rain Water

Trapping Rain Water

O(1) Version - 44ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = right = water = 0
        i, j = 0, len(height) - 1
        while i <= j:
            left, right = max(left, height[i]), max(right, height[j])
            while i <= j and height[i] <= left <= right:
                water += left - height[i]
                i += 1
            while i <= j and height[j] <= right <= left:
                water += right - height[j]
                j -= 1
        return water

test code

1
2
3
4
In [36]: s = Solution(); t = s.trap([0,1,0,2,1,0,1,3,2,1,2,1])
In [37]: t
Out[37]: 6

leet code

leetcode

Find Peak Element

Find Peak Element

Binary Search Version - 36ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left < right - 1:
            mid = (left + right) // 2
            if nums[mid - 1] < nums[mid] and nums[mid] > nums[mid + 1]:
                return mid
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid - 1
        return left if nums[left] >= nums[right] else right

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
In [7]: nums = [1,2,3,1]
In [17]: s = Solution(); t = s.findPeakElement(nums)
In [18]: t
Out[18]: 2
In [19]: nums = [1,2,1,3,5,6,4]
In [20]: s = Solution(); t = s.findPeakElement(nums)
In [21]: t
Out[21]: 5

leet code