26. Remove Duplicates from Sorted Array[E]

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Description

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        idx = 1
        if len(nums)==0:
            return 0
        for i in range(1,len(nums)):
            if nums[i] != nums[i-1]:
                nums[idx] = nums[i]
                idx +=1
        return idx

https://leetcode.com/problems/remove-duplicates-from-sorted-array/solution/

27. Remove Element[E]

Description

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        ls = len(nums)
        if ls == 0:
            return ls
        count = 0
        index = 0
        while index < ls - count:
            if nums[index] == val:
                nums[index] = nums[ls - 1 - count]
                count += 1
            else:
                index += 1
        return ls - count

33. Search in Rotated Sorted Array[M]

https://leetcode.com/problems/search-in-rotated-sorted-array/

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Solution

1

34. Find First and Last Position of Element in Sorted Array[M]

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Description

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non decreasing array.
  • -10^9 <= target <= 10^9

Solution

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/

35. Search Insert Position[E]

https://leetcode.com/problems/search-insert-position/

Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0

Solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, ll = 0, len(nums) - 1
        while l < ll:
            mid = int((l + ll) / 2)
            if nums[mid] < target:
                l = mid + 1
            else:
                ll = mid
        if nums[l] < target:
            return l + 1
        return l

66. Plus One[E]

https://leetcode.com/problems/plus-one/

Description

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution

1
2
3
4
5
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return [int(i) for i in str(int(''.join((str(i) for i in digits))) + 1)]
        # arrrrh, I am misunderstanding the problem, [1,2,5,9] --> [1,2,5,1,0]
        # return digits[:-1] + [str(i) for i in str(digits[-1] + 1)] 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        ls = len(digits)
        for index in reversed(range(ls)):
            if digits[index] < 9:
                digits[index] += 1
                # do not need to continue
                return digits
            else:
                # 10
                digits[index] = 0
        digits.insert(0, 1)
        return digits

78. Subsets[M]

https://leetcode.com/problems/subsets/

Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution

https://leetcode.com/problems/subsets/solution/

1
2
3
4
5
6
7
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        sub = [[]]
        for i in nums:
            for j in range(len(sub)):
                sub.append(sub[j]+[i])
        return sub

90. Subsets II[M]

https://leetcode.com/problems/subsets-ii/

Description

iven a collection of integers that might contain duplicates, *nums*, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution

1
2
3
4
5
6
7
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        sub = [[]]
        for i in nums:
            for j in range(len(sub)):
                sub.append(sorted(sub[j]+[i]))
        return  [list(s) for s in (set([tuple(l) for l in sub]))]

162. Find Peak Element[M]

https://leetcode.com/problems/find-peak-element/

Description

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

1
2
3
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

1
2
3
4
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Follow up: Your solution should be in logarithmic complexity.

Solution

https://leetcode.com/discuss/88467/tricky-problem-tricky-solution

1

169. Majority Element[E]

https://leetcode.com/problems/majority-element/

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2

Solution

https://leetcode.com/problems/majority-element/solution/

1

229. Majority Element II[M]

https://leetcode.com/problems/majority-element-ii/

Description

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

1
2
Input: [3,2,3]
Output: [3]

Example 2:

1
2
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution

1

283. Move Zeroes[E]

https://leetcode.com/problems/move-zeroes/

Description

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

1
2
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

Solution

https://leetcode.com/problems/move-zeroes/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # O(n)
        ls = len(nums)
        n_pos = 0
        for i in range(ls):
            if nums[i] != 0:
                temp = nums[n_pos]
                nums[n_pos] = nums[i]
                nums[i] = temp
                n_pos += 1

605. Can Place Flowers[E]

https://leetcode.com/problems/can-place-flowers/

Description

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

1
2
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

1
2
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won’t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won’t exceed the input array size.

Solution

https://leetcode.com/problems/can-place-flowers/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        count = 0
        for i in range(len(flowerbed)):
            curr = flowerbed[i]
            if i - 1 >= 0:
                curr += flowerbed[i - 1]
            if i + 1 < len(flowerbed):
                curr += flowerbed[i + 1]
            if curr == 0:
                count += 1
                flowerbed[i] = 1
                if count >= n:
                    return True
        return False

703. Kth Largest Element in a Stream[E]

https://leetcode.com/problems/kth-largest-element-in-a-stream/

Description

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

1
2
3
4
5
6
7
8
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note:
You may assume that nums’ length ≥ k-1 and k ≥ 1.

Solution

1

724. Find Pivot Index[E]

https://leetcode.com/problems/find-pivot-index/

Description

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of all the numbers to the left of the index is equal to the sum of all the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

1
2
3
4
5
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

1
2
3
4
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Constraints:

  • The length of nums will be in the range [0, 10000].
  • Each element nums[i] will be an integer in the range [-1000, 1000].

Solution

https://leetcode.com/problems/find-pivot-index/solution/

1
2
3
4
5
6
7
8
9
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        totalsum = sum(nums)
        leftsum = 0
        for i, v in enumerate(nums):
            if leftsum == totalsum - leftsum - v:
                return i
            leftsum += v
        return -1

962. Maximum Width Ramp[M]

https://leetcode.com/problems/maximum-width-ramp/

Description

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

1
2
3
4
Input: [6,0,8,2,1,5]
Output: 4
Explanation: 
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

1
2
3
4
Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: 
The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

  1. 2 <= A.length <= 50000
  2. 0 <= A[i] <= 50000

Solution

https://leetcode.com/problems/maximum-width-ramp/solution/

1
2
3
4
5
6
7
8
9
class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        ans = 0
        m = float('inf')
        # Sort index based on value
        for i in sorted(range(len(A)), key=A.__getitem__):
            ans = max(ans, i - m)
            m = min(m, i)
        return ans

832. Flipping an Image[E]

https://leetcode.com/problems/flipping-an-image/

Description

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

1
2
3
4
Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

1
2
3
4
Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

  • 1 <= A.length = A[0].length <= 20
  • 0 <= A[i][j] <= 1

Solution

https://leetcode.com/problems/flipping-an-image/solution/

1

836. Rectangle Overlap[E]

https://leetcode.com/problems/rectangle-overlap/

Description

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

Example 1:

1
2
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

1
2
Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Notes:

  1. Both rectangles rec1 and rec2 are lists of 4 integers.
  2. All coordinates in rectangles will be between -10^9and10^9.

Solution

https://leetcode.com/problems/rectangle-overlap/solution/

1