Posts published in “Algorithms”

花花酱 LeetCode 27. Remove Element

By zxi on October 2, 2018

Problem

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:

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:

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:

// 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:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int len = 0;

for (int num : nums)

if (num != val) nums[len++] = num;

return len;

}

};

Python3

class Solution:

def removeElement(self, nums, val):

l = 0

for num in nums:

if num != val:

nums[l], l = num, l + 1

return l

Problem

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:

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:

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:

// 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:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

const int n = nums.size();

if (n <= 1) return n;

int ans = 0;

int i = 0;

while (i < n) {

nums[ans++] = nums[i];

int j = i + 1;

while (j < n && nums[j] == nums[j - 1]) ++j;

i = j;

}

return ans;

}

};

花花酱 LeetCode 915. Partition Array into Disjoint Intervals

By zxi on September 30, 2018

Problem

Given an array A, partition it into two (contiguous) subarrays left and right so that:

Every element in left is less than or equal to every element in right.
left and right are non-empty.
left has the smallest possible size.

Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.

Example 1:

Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Note:

2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

Solution 1: BST

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua, 100 ms

class Solution {

public:

int partitionDisjoint(vector<int>& A) {

multiset<int> s(begin(A) + 1, end(A));

int left_max = A[0];

for (int i = 1; i < A.size(); ++i) {

if (*begin(s) >= left_max) return i;

s.erase(s.equal_range(A[i]).first);

left_max = max(left_max, A[i]);

}

return -1;

}

};

Solution 2: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 28 ms

class Solution {

public:

int partitionDisjoint(vector<int>& A) {

int left_max = A[0];

int cur_max = A[0];

int left_len = 1;

for (int i = 1; i < A.size(); ++i) {

if (A[i] < left_max) {

left_max = cur_max;

left_len = i + 1;

} else {

cur_max = max(cur_max, A[i]);

}

return left_len;

}

};

花花酱 LeetCode 88. Merge Sorted Array

By zxi on September 27, 2018

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

Solution:

Fill nums1 from back to front

Time complexity: O(m + n)

Space complexity: O(1) in-place

C++

// Author: Huahua

class Solution {

public:

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

int i = m - 1;

int j = n - 1;

int tail = m + n - 1;

while (j >= 0)

nums1[tail--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];

}

};

花花酱 LeetCode 911. Online Election

By zxi on September 25, 2018

Problem

n an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.

Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

Input: ["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
Output: [null,0,1,1,0,0,1]
Explanation: 
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

Note:

1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times is a strictly increasing array with all elements in [0, 10^9].
TopVotedCandidate.q is called at most 10000 times per test case.
TopVotedCandidate.q(int t) is always called with t >= times[0].

Solution: HashTable + Binary Search

Compute the leads for each t in times using a hash table.

binary search the upper bound of t, and return the lead of previous entry.

Time complexity: Constructor O(n), Query: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

class TopVotedCandidate {

public:

TopVotedCandidate(vector<int> persons, vector<int> times) {

vector<int> votes(persons.size() + 1);

int last_lead = persons.front();

for (int i = 0; i < persons.size(); ++i) {

if (++votes[persons[i]] >= votes[last_lead])

last_lead = persons[i];

leads_[times[i]] = last_lead;

}

int q(int t) {

return prev(leads_.upper_bound(t))->second;

}

private:

map<int, int> leads_; // time -> lead

};

Posts published in “Algorithms”

花花酱 LeetCode 27. Remove Element

Problem

Solution:

C++

Python3

Related Problems

花花酱 LeetCode 26. Remove Duplicates from Sorted Array

Problem

Solution:

C++

花花酱 LeetCode 915. Partition Array into Disjoint Intervals

Problem

Solution 1: BST

C++

Solution 2: Greedy

C++

花花酱 LeetCode 88. Merge Sorted Array

Problem

Solution:

C++

花花酱 LeetCode 911. Online Election

Problem

Solution: HashTable + Binary Search

C++