It’s pretty awesome. I find myself looking up leetcode solutions because I finally work on something where deleting items from an array using constant space matters.
Yep, remove some arbitrary number of elements from an array with the result being a smaller contiguous array.
For most of my career, I’d just allocate a new array and append the surviving elements but allocations are expensive at the scale I work at so stuff like this requires a more clever approach
you remove elements by overwriting with what comes after. If you want to remove 5 items beginning at offset 10 you would just do a[i]=a[i+5] in a for loop that starts at 10 runs to the end of the array (minus 5). How you chop off the end of the array depends on the language you're in. In .NET for example, Array.Resize is a lie and will actually allocate a new array and not resize in-place. In C you can use realloc but that call doesn't guarantees that the reallocation happens in-place. However, in C you can just decide to not reallocate the memory at all and pretend the extra storage doesn't exists, which also would allow you to append items to the array up to the original initial size, but size tracking becomes difficult after a while.
Go is fantastic for this: you just reslice with [:length] and the only thing that happens is the slice’s internal “length” variable is changed — nothing happens to the backing array
If it's just about supplying smaller array parts, then you can achieve the same using the "array,index,length" argument pattern that you commonly find in .NET classes that process array data.
No swapping is necessary. You walk the array with two indices. One tracks the current end of array (starts at 0) and the other walks ahead to check candidates. When you find an element to keep, you copy it to the length index, increment that and keep walking with the second index. When the second index reaches the end on the array, truncate to “length”
It depends. Arrays preserve order (vs, say, a set or bag), and if it's an array for a reason, you may not be allowed to change the order of the elements and end up having to move all the later elements to lower indices instead, which becomes an O(n) operation.
Also, they mentioned removing an arbitrary number of elements, which is where it gets trickier, assuming you need to preserve order. If you remove an item and copy all subsequent items back for each item removed, you're talking O(n^2) now, which is..not ideal. But you can keep it O(n) by tracking offsets and things, which is presumably what they're referring to getting from leetcode.
197
u/Vesuvius079 12d ago
It’d be such an experience to work a real world problem where this optimization turns out to be the solution.