80. Remove Duplicates from Sorted Array II (Medium)

 Remove Duplicates from Sorted Array II is a Medium level problem.


Given an array of integers sorted in non-decreasing (aka, increasing) order, remove all but TWO of each duplicate value IN PLACE and return the number of unique values in the list.

My solution to this was an adaptation to 26. Remove Duplicates From Sorted Array. It was relatively quick an easy to update indices to solve this.

Challenges were off-by-one bugs with my indexes. This solution would have benefited from some white-boarding.

class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
end = len(nums)-1
beg = end
dupeCount = 0
origCount = len(nums)

while (end > 0):
val = nums[end]
lookBack = val

while (beg > 0 and lookBack == val):
lookBack = nums[beg-1]
if lookBack == val:
beg -= 1
# beg is now the index of the first occurence of val
# If beg != end means we found some number of dupes
# If end - beg == 1 then we found exactly two dupes, so we keep them both.
# We only proceed to remove elements if there are more than two dupes.
if beg != end and end - beg != 1:
# Truncate nums by removing all the dupes, leaving just
# the first two occurences of val
nums[beg+2:] = nums[end+1:]

dupeCount += end-beg-1
# Shift the end pointer
end = beg - 1
beg = end

return origCount - dupeCount

Runtime: 48 ms. Beats 78.73% of users.
Memory: 16.64 MB. Beats 22.43% of users.

So just okay performance on runtime, but pretty weak performance on memory.

It is nice to have solved my first Medium using a solution from an Easy.

Comments

Post a Comment

Popular posts from this blog

846. Hand of Straights (medium)

Hand of Straights is a Medium level problem. Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards. Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise. Example 1: Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8] DISCUSSION: The first insight into this problem is related to groupSize and has two parts:  groupSize of 1 should always return True since groups of 1 are always straights. groupSize must divide the hand length. In other words: len(hand)%groupSize == 0. If group size does not divide handLength then the hand can clearly not be rearranged into groupSize groups. The second insight into this problem is related to my solution strategy, which is that each group should start...
Read more

409. Longest Palindrome (Easy)

Longest Palindrome is an Easy level problem. Given a string s consisting of uppercase or lowercase characters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive, so A is different from a. The key realization with this problem is that a palindrome of length greater than 1 will have an EVEN number of each character with the exception of the character right in the middle, which can appear once. The solution, then, is to count up how many times each letter appears in s, then add the even part of each count, then add 1 if any of the letters had an odd count. IE: "abccccdd" has the following counts: "a":1 "b":1 "c":4 "d":2 So the palindrome will have 4 "c"s, 2 "d"s and 1 of either "a" or "b" right in the middle, hence the length is 7. The problem does not ask us to generate the palindrome, only to calculate the length, which makes it easier. Run...
Read more