4

We have an array A of integers of size N. Given another array B which contains indices, where size of B <= N and 0<=B[i]<=N-1.

Now we have to remove all elements from array A at position B[i].

So with deletion we mean we are also shifting elements in array A.

Can someone help me in reaching to O(n) solution for this problem? And possibly O(1) space.

The first solution that comes to my mind is, traversing the array B and deleting elements in A sequentially( including shifting) but it is O(n^2).

Improve this question
8
  • 2
    Are the elements of B sorted in some order? If you're also shifting A, the order of elements in B are important. Commented Jun 9, 2011 at 15:42
  • Do you have any limitations of these numbers? I mean, can you use some special value to mark some element as "already deleted"? If so, this would be an easy one. Commented Jun 9, 2011 at 15:42
  • @Kiril, Marking elements as already visited/deleted is not allowed :( Commented Jun 9, 2011 at 15:45
  • @SubmittedDenied, The elements in B array need not be sorted. Commented Jun 9, 2011 at 15:47
  • 1
    Well, O(1) space and marking not allowed.. And even more - B is not sorted.. I'm not sure if this is possible at all. Commented Jun 9, 2011 at 15:49

5 Answers 5

Reset to default
3

Similar to iliaden's solution except you could do the removing of deleted elements in place.

int[] a = 
int[] b = 
int nullValue = 
for(int i: b) a[i] = nullValue;
int j=0;
for(int i=0; i < a.length; i++) {
    if(a[i] != nullValue)
       a[j++] = a[i];
}
// to clear the rest of the array, if required.
for(;j<a.length;j++)
   a[j] = nullValue;

note: a won't be shorter, but it avoid creating any more space. 'j' will have the number of valid entries in a

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Great, O(n) time and O(1) space. Perfect. Thanks a lot :)
I think this is about as good as it is possible to get, changing the size of an array is generally O(n) memory anyway (create new array, copy everything over). It might be worth going over the remaining elements N-j elements and writing nulls in there too.
This solution depends on the contents of A having some sort of null value. This isn't typically the case. Without a null value, you have to maintain the information about which elements are deleted separately, in a bit vector of some sort. And the second loop above is simply a less efficient version of std::remove_if.
@James, The OP has posted that he believes O(1) memory allocation is possible, this implies that it should be done without allocating additional memory proportional to the size. In my experience a null value is always possible in business logic. I don't see how std::remove_if is more efficient than the second loop. (Now have I moved the second loop out ;)
In my experience, null values aren't always possible; that's why Fallible classes (or boost::optional, or Maybe) were invented. But it depends on the application, and the sort of things he's storing in the array (which he didn't tell us). Without null values, I don't think there is a solution without additional memory; you have to store the additional information somewhere. As for remove_if, look at it; typically, it uses std::find_if to find where to start copying, which avoids some unnecessary self-assignments.
0

in O(n) space, you can do:

  1. traverse array A deleting every element at b[i] (no shifting, O(n))

  2. create a new array C, copy all the non-empty elements from A into C sequentially (also O(n))

  3. return array C or copy it back onto a cleared array A (O(n)) . thus you get to do it in O(n) tim and O(n) space

Improve this answer

1 Comment

Thanks for reply. This will work but I am looking for something in O(1) for space and O(n) for time.
0

No marking, O(n) time, but also O(n) space, in pseudo-code:

// create a boolean array indicating which elements are to be deleted
D = new boolean[N]
fill(D, false)
for (b in B) {
  D[b] = true
}

// compact `A in place
src = 0
dest = 0
while (src < N) {
  if (!D[src]) {
    A[dest++] = A[src]
  }
  src++
}

new_N = dest
Improve this answer

Comments

0

if you can assume b is sorted you can shift as you iterate (you can sort the b in O(n*log(n)) if not)

int[] b;
int[] a;
int first=0,bInd=0;
for(int i = 0;i<a.length;i++){
    if(bInd>=b.length || b[bInd]!=i){
        a[first]=a[i];
        first++;
    }else{
        bInd++;
    }
}
Improve this answer

4 Comments

You can't sort B as the positions of items in A changes when you shift A. B might be [0, 0], indicating that you need to remove the first two elements in A.
@submitted I'm assuming here the element in B are exact indices from the array A BEFORE ANY DELETIONS so b=[0,0] would be either invalid or mean that only the first should be removed
@submittedDenied, Sorting wont effect the real solution. The indexes in B are wrt initial Array. Shifting wont have any effect on Array B.
@learner Sorting will allow you to do the deletions in a back to front order. So a deletion will not affect the indexes of any yet to delete object.
0

Two obvious solutions: sort B in reverse order before starting, so you always delete the highest index (and so never shift a deleted element), or iterate through B to create a bitmap of elements to delete (and then do those in the reverse order). The first requires an additional O(lg n) step beforehand, and the second additional space. But I'm not sure there are any better alternatives.

Improve this answer

2 Comments

The order of B matters, you can't sort it. Also, even if it were in ascending or descending order, you'd need to shift elements that are to the right of the deleted element (ie, that have a higher index) to the left.
@SubmittedDenied Whenever you actually remove an element from an std::vector (unless it's the last), you have to shift other elements. But functions like std::remove_if don't actually remove elements; you remove a block of elements at the end once they've shifted the elements to be kept to the start. The reason for starting from the back is that you don't invalidate unprocessed indexes. If you can't sort B, then the only solution is to use the bit vector; after that, you can use std::remove_if and erase, or copy_if.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.