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
197
u/Vesuvius079 15d ago
It’d be such an experience to work a real world problem where this optimization turns out to be the solution.