CODEWITHSUNDEEP
algorithmlistgrouping
mlemboy
mlemboy

Reputation: 95

Group list elements by difference

Let's say I've a list,

(1,2,4,6,7,8,10,23,34,35,67,69,70)

How can I group the elements in the list with difference of 1 or less together, so the output would look like this,

((1,2),(4),(6,7,8),(10),(23),(34,35),(67),(69,70))

I tried to come up with few iterative solutions but failed every time because the state of list changes if we just delete the elements during the iteration. Anyway, I think I'm really stuck and can not solve this on my own. Any help is appreciated.

Any programming language is okay for the solution, all I'm looking for is a direction to go in. I don't want the full solution. Just some incomplete pseudo code which can help me solve this faster as this is very tiny part of what I'm trying to do. Just a name of an algorithm is fine too. :)

Upvotes: 0

Views: 57

Answers (2)

RaffleBuffle
RaffleBuffle

Reputation: 5455

Java not Ruby, but hopefully it translates fairly easily:

int[] arr = {1,2,4,6,7,8,10,23,34,35,67,69,70};

for(int i=1, j=0; i<=arr.length; i++)
{
  if(i == arr.length || arr[i]-1 != arr[i-1])
  {
    System.out.printf("%s ", Arrays.toString(Arrays.copyOfRange(arr, j, i)));
    j = i;
  }
}

Output:

[1, 2] [4] [6, 7, 8] [10] [23] [34, 35] [67] [69, 70]

Upvotes: 1

mlemboy
mlemboy

Reputation: 95

Ok, I think I solved it. But still seems ugly to me. I used Ruby,

array = [1,2,4,6,7,8,10,23,34,35,67,69,70]

last_index_before = array.size - 1
arr = []

# Can not use map because of the break maybe?
(0..last_index_before).each do |_|
  element = array.delete_at(0)
  break if element.nil? # We reached the end
  results = [element]

  next_element = array[0]
  while !next_element.nil? && (next_element - element) <= 1
    results << array.delete_at(0)
    element = next_element
    next_element = array[0]
  end
  arr << results
end

p arr

The output,

[[1, 2], [4], [6, 7, 8], [10], [23], [34, 35], [67], [69, 70]]

Upvotes: 0

Related Questions