Algorithms

As I am working through LeetCode to make sure I am improving my algorithm skills I figured, why not bring y'all along?!

Each problem I present I worked on for 30 minutes and then researched the rest of the way to find better or more efficient or just plain old correct solutions. The purpose is to replicate the interview process and refine my problem solving skills.

The Problem:

Given an integer array nums sorted in non-decreasing order,
remove the duplicates in-place such that each unique element
appears only once. The relative order of the elements should
be kept the same. Then return the number of unique elements in
nums.

Consider the number of unique elements of nums to be k, to get
accepted, you need to do the following things:

Change the array nums such that the first k elements of nums
contain the unique elements in the order they were present in
nums initially. The remaining elements of nums are not
important as well as the size of nums.
Return k.

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

Now when I first looked at this problem I thought 'No problem! I have the perfect solution'

def remove_duplicates(nums)
  return 0 if nums.empty?

  nums.uniq!.length
end

This would have been perfect except for the fact that it wasn't. Because it didn't pass all the tests behind the method. As a new dev you might be familiar with the death spiral of trying to figure out why my 'flawless' logic wasn't working. Instead of just trying to find an alternative solution. Unfortunately, I ran out of time BUT I did learn a lot about how I should have approached this problem.

PSUEDO CODE THE PROBLEM!

The reason being that I was trying to problem solve and code at the same time. While I think I know how to code decently well. I should have broken down the problem in english because there were so many clues in the problem that I just missed because I 'thought I knew what it was asking'.

In the end that was a huge time waster and just proved to be a inefficient way of solving the problem.

What was the Solution?

def remove_duplicates(nums)
  return 0 if nums.empty?

  k = 1
  i = 1

  while i < nums.length
    if nums[i] != nums[k - 1]
      nums[k] = nums[i]
      k += 1
    end
    i += 1
  end
  k
end

** INPUT NOTES **

Above was the solution I used and below is the reasons why this works.

Outside of the while loop I have two variables instantiated. the k variable is the count of unique values and i is what value we are in the length of the array.

I chose a while loop because comparing the i (array length count) to the length of the nums array (method argument). I will go into more detail about why I chose the while loop versus the .each enumerator a little be later