75. Sort Colors[M]

https://leetcode.com/problems/sort-colors/

Description

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

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

Follow up:

  • A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
  • Could you come up with a one-pass algorithm using only constant space?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = {0:0, 1:0, 2:0}
        
        for i in nums:
            count[i] = count[i] + 1
        idx = 0
        for j in range(3):
            for k in range(count[j]):
                nums[idx], idx = j, idx + 1
        return

80. Remove Duplicates from Sorted Array II[M]

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

Description

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice 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,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 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,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 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

153. Find Minimum in Rotated Sorted Array[M]

https://leetcode.com/problems/find-minimum-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]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

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

Example 2:

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

Solution

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/solution/

1
2
3
4
5
6
7
8
9
10
def findMin(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    while nums[left] > nums[right]:
        mid  = (left + right) // 2
        if nums[mid] < nums[right]:
            right = mid
        else:
            left = mid + 1
    return nums[left]

215. Kth Largest Element in an Array[M]

https://leetcode.com/problems/kth-largest-element-in-an-array/

Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Solution

238. Product of Array Except Selfs[M]

https://leetcode.com/problems/product-of-array-except-self/

Description

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

1
2
Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Solution

https://leetcode.com/problems/product-of-array-except-self/solution/

1
2
3
4
5
6
7
8
9
10
class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
      ans = [1] * len(nums)
      for i in range(1, len(nums)):
          ans[i] = ans[i - 1] * nums[i - 1]
      right = 1
      for i in range(len(nums) - 1, -1, -1):
          ans[i] *= right
          right *= nums[i]
      return ans

349. Intersection of Two Arrays[E]

https://leetcode.com/problems/intersection-of-two-arrays/

Description

Given two arrays, write a function to compute their intersection.

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

1
2
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

Solution

https://leetcode.com/problems/intersection-of-two-arrays/solution/

1
2
3
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

350. Intersection of Two Arrays II[E]

https://leetcode.com/problems/intersection-of-two-arrays-ii/

Description

Given two arrays, write a function to compute their intersection.

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

1
2
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        res = []
        pos1 = pos2 = 0
        while pos1 < len(nums1) and pos2 < len(nums2):
            if nums1[pos1] == nums2[pos2]:
                res.append(nums1[pos1])
                pos1 += 1
                pos2 += 1
            elif nums1[pos1] < nums2[pos2]:
                pos1 += 1
            else:
                pos2 += 1
        return res

384. Shuffle an Array[M]

https://leetcode.com/problems/shuffle-an-array/

Description

Shuffle a set of numbers without duplicates.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

Solution

https://leetcode.com/problems/shuffle-an-array/solution/

1

453. Minimum Moves to Equal Array Elements[E]

https://leetcode.com/problems/minimum-moves-to-equal-array-elements/

Description

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

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

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Solution

1
2
3
4
5
6
7
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        if nums is None or len(nums) == 0:
            return 0
        min_num = min(nums)
        return sum([i - min_num for i in nums])

665. Non-decreasing Array[E]

https://leetcode.com/problems/non-decreasing-array/

Description

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if nums[i] <= nums``[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

1
2
3
Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

1
2
3
Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

Constraints:

  • 1 <= n <= 10 ^ 4
  • - 10 ^ 5 <= nums[i] <= 10 ^ 5

Solution

1

697. Degree of an Array[E]

https://leetcode.com/problems/degree-of-an-array/

Description

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

1
2
3
4
5
6
7
Input: nums = [1,2,2,3,1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

1
2
3
4
5
Input: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

Constraints:

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        left, right, count = {}, {}, {}
        for i, x in enumerate(nums):
            if x not in left: left[x] = i
            right[x] = i
            count[x] = count.get(x, 0) + 1

        ans = len(nums)
        degree = max(count.values())
        for x in count:
            if count[x] == degree:
                ans = min(ans, right[x] - left[x] + 1)

        return ans

852. Peak Index in a Mountain Array[E]

https://leetcode.com/problems/peak-index-in-a-mountain-array/

Description

Let’s call an array A a mountain if the following properties hold:

  • A.length >= 3
  • There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

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

Example 2:

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

Note:

  1. 3 <= A.length <= 10000
  2. 0 <= A[i] <= 10^6
  3. A is a mountain, as defined above.

Solution

https://leetcode.com/problems/peak-index-in-a-mountain-array/solution/

1

905. Sort Array By Paritys[E]

https://leetcode.com/problems/sort-array-by-parity/

Description

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

1
2
3
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

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

Solution

1
2
3
4
5
6
7
8
9
10
class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        lo, hi = 0, len(A) - 1
        while lo < hi:
            if A[lo] % 2 > A[hi] % 2:
                A[lo], A[hi] = A[hi], A[lo]
            if A[lo] % 2 == 0: lo += 1
            if A[hi] % 2 == 1: hi -= 1
        return A

922. Sort Array By Parity II[E]

https://leetcode.com/problems/sort-array-by-parity-ii/

Description

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

1
2
3
Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

  1. 2 <= A.length <= 20000
  2. A.length % 2 == 0
  3. 0 <= A[i] <= 1000

Solution

https://leetcode.com/problems/sort-array-by-parity-ii/solution/

1