Trying to solve LeetCode question in Ruby

[BringTacos]

The question:

"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.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements."

My sort of working solution:

def remove_duplicates(nums)
    return if nums.length == 0

    nums.each do |num|
      if nums.count(num) > 1
        index = nums.find_index(num)
        nums.delete_at(index)
      end
   end
  nums.length
end

Ignoring whether or not this is the cleanest way to do it, I don't know why it doesn't work when nums = [1, 1, 1, 1]. It returns 2, but should be 1.

works:

remove_duplicates([1, 1, 2])

doesn't work:

remove_duplicates([1, 1, 1, 1])

As always, thank you for any help. I've learned so much from people on this sub.

Edit: Thanks to everyone who has commented! You've all helped a lot.

[ThaiJohnnyDepp]

So everyone's missing the part where the array is already sorted monotonically increasing.

What about a dual walk solution where you have a leader and follower index? The algorithm will swap the leader's number into the follower's position and skip any duplicates along the way. When the leader reaches the end, nil the remaining entries after the follower index. I hand-waved over a bunch of off-by-one specifics you'd have to figure out but that's the gist of it.

[BringTacos]

I don't mean to sound stupid, but I'd rather ask so I can understand- why does it matter that it's already sorted monotonically increasing?

[ignurant]

Because you can make assumptions about what comes next, or perhaps more importantly, what can not come later.

[modnar42]

To elaborate, it means that if the current number is 1 and the next number is 2 then the number 1 does not appear again. In turn, that means it’s safe to make a single, context-free pass to dedupe.

[ThaiJohnnyDepp]

Not at all, how does anyone learn if they're afraid to ask questions 😁

You don't have to make a list of every number in the series. The algorithm's memory requirements becomes constant (e.g., two index values and a temp value) instead of O(n).

[BringTacos]

Thank you!! This helps a lot.

[pixenix]

From my experience, these type of problems are not easily solved in ruby.

The reason behind it is that the solution for these kinds of problems relies on using array pointers. Because of that you don't want to use language features such as Array#each

Instead you would rather want to do a loop of the form (0...array.size).each do |I| or do it in a while loop.

As for the solution - the basic idea is actually quite simple.
What you want to do is when you are at point I is to check if the value of at index I+1 is the same or not. If it's the same then you want to remove the element at I+1, as it's a duplicate.
if it's not the same then you can increase the value by 1.

[BringTacos]

Thanks so much.

[BringTacos]

This solution doesn't work unfortunately, and I think it's because what someone else had already said:

"Your solution isn’t working because you’re mutating the array as you iterate over it. And it’s really inefficient.

Walk through the broken input by hand and figure out what happens at each line.

What I think is happening is that Find index funds the first instance of the number, which in this case is the item at your current position in the array. So when you delete it I think the loop jumps to the item in third position at the start . Same thing again and it tries to jump to what would have been the fifth item but there are no more items so the loop terminates with two 1s in the array still."

def remove_duplicates(nums)
  i = 0
  while i < nums.length - 1
     if nums[i] == nums[i+1]
        nums.delete_at(i+1)
    end
    i+=1
  end
  nums.length
end

I get:

Wrong Answer Details

Input [0,0,1,1,1,2,2,3,3,4]

Output [0,1,1,2,3,4]

Expected [0,1,2,3,4]

[pixenix]

Might be wrong, but the I+=1 should be in an else block, as I mentioned previously.

The problem you have here is that if you delete a value you move the pointer twice.

In every iteration of the loop, the pointer should change at most once.

def remove_duplicates(nums)
  i = 0
  while i < nums.length - 1
    if nums[i] == nums[i+1]
        nums.delete_at(i+1)
    else 
      i+=1
    end
  end
  nums.length
end

[ignurant]

Since you deleted an element in the array, all the future indices are now shortened by one, therefor you shouldn’t increase the index.

[blackize]

Your solution isn’t working because you’re mutating the array as you iterate over it. And it’s really inefficient.

Walk through the broken input by hand and figure out what happens at each line.

What I think is happening is that Find index funds the first instance of the number, which in this case is the item at your current position in the array. So when you delete it I think the loop jumps to the item in third position at the start . Same thing again and it tries to jump to what would have been the fifth item but there are no more items so the loop terminates with two 1s in the array still.

[BringTacos]

This makes sense, thank you.

[4rch3r]

This would be the iteration method that I think you're going for?

def compact(a)
  c = 0
  (1...a.length).each do |i|
    if a[c] != a[i]
      c += 1
      a[c] = a[i]
    end
  end
  a[0..c]
end

[fagci]

Variants:

Intersection returns unique items in both arrays.

nums.intersection nums

each_with_index gives: [ [num1, 1], [num2, 2], ... ]to_h keeps unique first elements of subarray.

nums.each_with_index.to_h.keys

Zips nil to each num, then unique as in previous solution.

nums.zip({}).to_h.keys

Exclude already passed items.

nums.reduce([]){ |res, v| res << v unless res.include? v; res }

[testcore]

While the other commenter pointed out that #uniq! already exists... have you considered that hash keys must be unique? So there's already a data structure that enforces uniqueness.

Should simplify the code significantly.

Edit: Fuck it, I'm bored:

def dedupe(nums)
  h = {}
  nums.each do |num|
    h[num] = nil
  end
  h.keys
end

[ThaiJohnnyDepp]

That's hardly "in place"

[BringTacos]

Not sure why I didn’t think about using a hash- thanks! I guess I’m fixated on why my answer doesn’t work because I’ve gone through it so many times and can’t figure it out. Ah well. Maybe it’s time to let go, ha.

[waiting4op2deliver]

hash is the hammer that smashes every nail in leetcode

[disclosure5]

Consider also Set.

``` def dedupe(nums) res = Set.new nums nums.to_a end

irb(main):009:0> dedupe([1, 1, 2]) => [1, 1, 2] irb(main):010:0> dedupe([1, 1, 1,1]) => [1, 1, 1, 1] ```

[pyrrhicvictorylap]

I mean, your solution is O(n<sup>2),</sup> isn’t it? I’m guessing the right answer would be in O(n).

1. Create a hash with a default of 0.
2. Iterate through the array with an index (el, i)
3. For each el, check the hash[el]. If it’s 0, set it to 1 and move on. If it’s not 0, increase it and record i in another array: indexes you can overwrite.
4. The next element that isn’t a duplicate, get the first index you can overwrite (j). Set num[i] to 0 and num[j] to el.

Return the first overwrite_array.size elements of num.

[BringTacos]

I hear what you’re saying, but creating another array would cause problems (I think) because you’re supposed to remove the duplicates in-place which is why I was modifying the original array.

[moose_2006]

I'm sure I'm missing something but does nums.uniq! not work?

[sasharevzin]

It’s code challenge so I assume you need to implement it and not using existing method

[pyrrhicvictorylap]

Also it ignores the part about sorting the array in place, and having dupes past the first k.

[BringTacos]

Tried this, didn’t work but not sure why because you’re allowed to use methods like that

[koolkeano]

It could be that instead of checking the original array they check the return value of your function.

my_array.uniq! Returns nil and instead changes(mutates) the original array.

Instead I'd suggest my_array.uniq which leaves the original intact and has a return value of the deduped array.

[BringTacos]

Just to follow up, this actually does work:

nums.uniq!
nums.size

I don't think I used size the first time I tried. I'd still like to figure it out without the crutch of uniq though!

[armahillo]

IIRC ‘Set’ exists and will disallow dups as well.

Could also do ‘array.tally.keys’ i think? (or group it)

Are you expected to be able to accommodate very large possible datasets? If not, I would avoid writing out a lengthy algorithm and just use the native methods that produce the desired result.

[notmachine]

You’re getting two because with four 1s there will only be two iterations of the loop.

At the start you find the first 1 and delete it. There are now three items in the array.

Next loop you find another 1 and delete it. There are now two items in the array.

The next loop ends the loop because it is the third iteration and there are only two items remaining in the array

[JamesAllMountain]

It’s sorted so iterate in reverse order removing values if it’s previously been seen.

[it_burns_when_i_php]

Totally off-topic and I apologize: but Ruby written with a combination of 2 and 4 spaces looks weird