Program to find contiguous intervals of a unique array in Python

Question

Program to find contiguous intervals of a unique array in Python

PythonServer Side ProgrammingProgramming

---

---

Suppose we have a list of unique numbers called nums. We have to find a sorted 2D matrix of numbers where each list represents an inclusive interval summarizing number that are contiguous in nums.

So, if the input is like nums = [10, 11, 12, 15, 16, 17, 28, 30], then the output will be [[10, 12], [15, 17], [28, 28], [30, 30]], as in the list [10 to 12], [15 to 17] are contiguous, and 28 and 30 are there, they are represented as [28 to 28] and [30 to 30].

To solve this, we will follow these steps−

• sort the list nums

• insert infinity at the end of nums

• ans:= a new list

  
  

• l:= nums[0]

• for i in range 1 to size of nums, do

  • if nums[i] is not same as nums[i-1] + 1, then

    • insert [l, nums[i-1]] at the end of ans

    • l:= nums[i]

• return ans

Let us see the following implementation to get better understanding−

 Live Demo

Example

class Solution:
def solve(self, nums):
   nums.sort()
   nums.append(1e9)
   ans=[]
   l=nums[0]
   for i in range(1,len(nums)):
      if nums[i] != nums[i-1] + 1:
         ans.append([l, nums[i-1]])
         l=nums[i]
   return ans
ob = Solution()
nums = [10, 11, 12, 15, 16, 17, 28, 30]
print(ob.solve(nums))

Input

[10, 11, 12, 15, 16, 17, 28, 30]

Output

[[10, 12], [15, 17], [28, 28], [30, 30]]

Arnab Chakraborty

Published on 05-Oct-2020 18:18:39

Previous Page Print Page

Next Page  

Advertisements