Why isnt this recursive algorithm working properly

Question

Ive written a recursive algorithm to delete any duplicates from a sorted list

def removeDuplicates(nums):
        def helper(nums,value=1):
            if value == len(nums):
                return nums
            if(nums[value] == nums[value-1]):
                del nums[value]
                return helper(nums,value+1)
            else:
                return helper(nums,value+1)
        return helper(nums)

For an input of [0,0,1,1,1,2,2,3,3,4], an output of [0,1,2,3,4] is expected. But instead an output of [0,1,1,2,3,4] is supplied Why isnt it working for triplets

When you delete an item, realise that the next item after that ends up at the index you just deleted, so you should not make the recursive call with `value+1`, but with `value`. Secondly, there is a much easier way to do all this: [remove duplicates](https://stackoverflow.com/questions/7961363/removing-duplicates-in-lists) — trincot, Feb 14 '22 at 20:14
@jarmod yes, but its an algorithmic problem on leetcode, that i have to solve manually — Noble Eugene, Feb 14 '22 at 20:18
Since you are doing this recursively for what seems like a study exercise, you might consider doing it in a way that does not mutate the original list. This would be more in line with functional programming practices and would also simplify the code. — Mark, Feb 14 '22 at 20:23
Yes @Mark, but the question demands we perform an in-place algorithm, rather that awarding extra space to a new array — Noble Eugene, Feb 14 '22 at 20:25

Eli Harold · Accepted Answer · 2022-02-14T20:24:12.763

When you delete a value from the list the size changes so you do not need to increment value:

def removeDuplicates(nums):
        def helper(nums,value=1):
            if value == len(nums):
                return nums
            if(nums[value] == nums[value-1]):
                del nums[value]
                return helper(nums,value) #notice the change here
            else:
                return helper(nums,value+1)
        return helper(nums)

This section of code:

del nums[value]
return helper(nums,value+1)

Causes the function to "skip" a value because an element is removed (changing the item at the index value) and value is incremented (also changing which item is at index value.)

So it should be:

del nums[value]
return helper(nums,value)

New code output:

[0, 1, 2, 3, 4]

However the best way to get the unique values would be:

list(set(my_list)) #best
#or
list({k: '' for k in test}.keys())

removeDuplicates([]) => kablooey – rici Feb 14 '22 at 21:26 — rici, Feb 14 '22 at 21:26

Why isnt this recursive algorithm working properly

1 Answers1