How to remove range from an array

Question

I'm trying to find something equivalent to remove_range (which does not exist of course) as shown below. Seems there is no easy way to implement this functionality.

a = [0,2,8,2,4,5,]
b = a.remove_range(1,2) #remove items between index 1 and 2 ,inclusively
#expect b == [0,2,4,5]
b = a.remove_range(3,4)
#expect b == [0,2,8,5]

Please test at least above two cases before posting your solution :)

Suppose the size of the range is M, this operation should requires O(1) space and O(N-M) time complexity.

EDIT: I see people keep posting the a - a[range]. But it is not correct, that is to remove the elements exists in a[range], not to remove the the element belongs to range.

a - a[1..2] will return [0, 4, 5]. However,we want to keep the 3rd element which is 2.

Is a Ruby API/grammar question or a coding/algorithm question? — coderz
– coderz, Commented May 12, 2015 at 2:21
I disagree that it "does not exist." It's just not named what you think it is. — David Hoelzer
– David Hoelzer, Commented May 12, 2015 at 2:32
+David Hoelzer I'm happy to know it is there. What is the name? — pierrotlefou
– pierrotlefou, Commented May 12, 2015 at 2:48
In your example, a never changes, that means you have to copy the result to another array, right? Then how to achieve O(1) space complexity? — coderz
– coderz, Commented May 12, 2015 at 3:18
@coderz you are right. There maybe simply no way to achieve O(1) with Ruby. I was just trying to set that as a target, which can be achieved in c/c++. — pierrotlefou
– pierrotlefou, Commented May 12, 2015 at 4:18

David Grayson · Accepted Answer · 2015-05-12 03:48:40Z

3

You can do some cool tricks with the Enumerable module:

a = [0, 2, 8, 2, 4, 5]
r = 1..2
a.reject.with_index { |v, i| r.include?(i) }  # => [0, 2, 4, 5]

Note that this does not modify the original array, but returns a new one. You can use reject! if you want to modify the array.

answered May 12, 2015 at 3:48

David Grayson

88.1k24 gold badges159 silver badges195 bronze badges

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

3 Comments

pierrotlefou Over a year ago

this is tricky, I didn't know the .reject.with_index stuff. Cool one.

Cary Swoveland Over a year ago

I hear someone saying, "Why didn't Grayson use Range#cover? instead of Range#include?, which checks each element in the range?". Ah, but include? is smart enough to know that, like cover?, it can just use the endpoints when, as here, they are numeric.

Tom Over a year ago

Worked nicely for me!

Edgar Mkaka Joel · Accepted Answer · 2015-05-16 19:02:18Z

2

# Use: array.slice!(range)
a = [0,2,8,2,4,5,]

a.slice!(1..2)
a # => [0, 2, 4, 5]

Or for indices range 3 to 4

a.slice!(3..4)
a # => [0, 2, 8, 5]

edited May 16, 2015 at 19:02

answered May 12, 2015 at 3:57

Edgar Mkaka Joel

964 bronze badges

Comments

David Hoelzer · Accepted Answer · 2015-05-12 02:31:28Z

1

This is built into the array class. Just subtract the piece that you don't want:

2.0.0-p353 :001 > ar = [0,2,8,2,4,5]
=> [0, 2, 8, 2, 4, 5] 
2.0.0-p353 :002 > ar - ar[2..3]
=> [0, 4, 5]

answered May 12, 2015 at 2:31

David Hoelzer

16.4k4 gold badges54 silver badges73 bronze badges

Comments

alebruck · Accepted Answer · 2015-05-12 04:32:34Z

1

class Array
  def remove_range(f,l)
    self[0..f-1].concat(self[l+1..-1])
  end
end

a = [0,2,8,2,4,5]
b = a.remove_range(1,2)
[0, 2, 4, 5]
c = a.remove_range(3,4)
[0, 2, 8, 5]

edited May 12, 2015 at 4:32

answered May 12, 2015 at 3:50

alebruck

4341 gold badge8 silver badges15 bronze badges

3 Comments

pierrotlefou Over a year ago

Yeah, I think it is the most straightforward (not the coolest) way :)

Dave Newton Over a year ago

@pierr Beware the +, though, unless your arrays are always short.

alebruck Over a year ago

Updated + to concat based on @DaveNewton note

ShallmentMo · Accepted Answer · 2015-05-12 07:43:39Z

1

class Array
  def remove_range(sp, ep)
    raise ArgumentError if sp < 0 || ep > size - 1
    slice(0...sp).concat(slice(ep+1..-1))
  end
end

Thank Cary Swoveland for his good advise

edited May 12, 2015 at 7:43

answered May 12, 2015 at 3:18

ShallmentMo

4491 gold badge4 silver badges16 bronze badges

2 Comments

Cary Swoveland Over a year ago

You may wish to raise an ArgumentError exception rather than returning false. The rest could alternatively be expressed slice(0...sp).concat(slice(ep+1..-1)). Array#concat is more efficient than + because it avoids the creation of two temporary arrays.

Cary Swoveland Over a year ago

A small point: when an if statement has just one line between if and end, some prefer writing (for example): raise ArgumentError if sp < 0 || ep > size - 1.

pangpang · Accepted Answer · 2015-05-12 03:32:01Z

0

a = [0,2,8,2,4,5]    
j = 1

(3..4).each do |i|
    j == 1 ? a.delete_at(i) : a.delete_at(i-1)
    j += 1
end

b = a
[0, 2, 8, 5]

edited May 12, 2015 at 3:32

answered May 12, 2015 at 2:47

pangpang

8,86915 gold badges67 silver badges99 bronze badges

2 Comments

coderz Over a year ago

delete_at operation is O(n) time complexity(see stackoverflow.com/questions/28510123/…), disobey the time complexity requirement.

Cary Swoveland Over a year ago

If you wish to delete elements, you must delete at the same index so many times or delete by index from highest to lowest index. Note that mutates the array.

Rots · Accepted Answer · 2015-05-12 04:08:50Z

0

Tried something funky with string manipulation. I think it's O(4*M) though if that's even a thing!

a.join.gsub(/#{a.join[1..2]}/,'').split('').map{|i| i.to_i}
=> [0, 2, 4, 5]
a.join.gsub(/#{a.join[3..4]}/,'').split('').map{|i| i.to_i}
=> [0, 2, 8, 5]

answered May 12, 2015 at 4:08

Rots

5,5964 gold badges47 silver badges51 bronze badges

Collectives™ on Stack Overflow

How to remove range from an array

7 Answers 7

3 Comments

Comments

Comments

3 Comments

2 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

3 Comments

Comments

Comments

3 Comments

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related