Week 1: Greedy Algorithm

Greedy Algorithm is very unlikely to appear in a coding interview. That means, you don’t have to learn that hard on this topic. Your task in this week is just to memorize the following solutions, then you are good to go.

1. Majority Element

LeetCode #169: Majority Element

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:

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

Example 2:

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

Algorithm:

The main idea is that if we eliminate every pair of majority element and non-majority element, the majority element will still be majority in the new list, since it appears more than ⌊ n/2 ⌋ times. The algorithm is the following: suppose the first element in nums is the majority element, and initialize count to 1. Loop the rest of nums. If the next element is still the same, increment count; otherwise, decrement count. If count is decreased to 0, suppose the next element is the majority element, and keep looping. The code is here:

Solution:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        majority = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if majority == nums[i]:
                count += 1
            else:
                count -= 1
            if count == 0:
                if i == len(nums):
                    break
                else:
                    majority = nums[i + 1]
        return majority

Analysis:

This algorithm uses a for loop that runs n - 1 times, and all operations inside the for loop takes time O(1), so the overall running time is O(n). It is also an in-place algorithm, thus takes O(1) space.

2. Create Maximum Number

LeetCode #321: Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

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

Example 2:

Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output:
[6, 7, 6, 0, 4]

Example 3:

Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output:
[9, 8, 9]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s