Get ranges where values are not None

Question

The Goal

I would like to get the ranges where values are not None in a list, so for example:

test1 = [None, 0, None]
test2 = [2,1,None]
test3 = [None,None,3]
test4 = [1,0,None,0,0,None,None,1,None,0]

res1 = [[1,1]]
res2 = [[0,1]]
res3 = [[2,2]]
res4 = [[0,1],[3,4],[7,7],[9,9]]

What I have tried

This is my super lengthy implementation, which does not perfectly work...

def get_not_None_ranges(list_):
    # Example [0, 2, None, 1, 4] -> [[0, 1], [3, 4]]
    r = []
    end_i = len(list_)-1
    if list_[0] == None:
        s = None
    else:
        s = 0
        
    for i, elem in enumerate(list_):
        if s != None:
            if elem == None and end_i != i:
                r.append([s,i-1])
                s = i+1
            if end_i == i:
                if s > i:
                    r=r
                elif s==i and elem == None:
                    r=r
                else:
                    r.append([s,i])
        else:
            if elem != None:
                s = i
            if end_i == i:
                if s > i:
                    r=r
                else:
                    r.append([s,i])
            
    return r 

As you can see the results are sometimes wrong:

print(get_not_None_ranges(test1))
print(get_not_None_ranges(test2))
print(get_not_None_ranges(test3))
print(get_not_None_ranges(test4))


[[1, 2]]
[[0, 2]]
[[2, 2]]
[[0, 1], [3, 4], [6, 5], [7, 7], [9, 9]]

So, I was wondering if you guys know a much better way to achieve this?

Answer 1

Use itertools.groupby:

from itertools import groupby

test1 = [None, 0, None]
test2 = [2, 1, None]
test3 = [None, None, 3]
test4 = [1, 0, None, 0, 0, None, None, 1, None, 0]


def get_not_None_ranges(lst):
    result = []
    for key, group in groupby(enumerate(lst), key=lambda x: x[1] is not None):
        if key:
            index, _ = next(group)
            result.append([index, index + sum(1 for _ in group)])
    return result


print(get_not_None_ranges(test1))
print(get_not_None_ranges(test2))
print(get_not_None_ranges(test3))
print(get_not_None_ranges(test4))

Output

[[1, 1]]
[[0, 1]]
[[2, 2]]
[[0, 1], [3, 4], [7, 7], [9, 9]]

Answer 2

Using first and last of each group of not nones:

from itertools import groupby

def get_not_None_ranges(lst):
    result = []
    for nones, group in groupby(enumerate(lst), lambda x: x[1] is None):
        if not nones:
            first = last = next(group)
            for last in group:
                pass
            result.append([first[0], last[0]])
    return result

Answer 3

You just need to iterate over the list, and check for two conditions:

1. If the previous element is None and the current element is not None, start a new "range".
2. If the previous element is not None and the current element is None, end the currently active range at the previous index.

def gnnr(lst):
    all_ranges = []
    current_range = []
    prev_item = None

    for index, item in enumerate(lst):
        # Condition 1
        if prev_item is None and item is not None:
            current_range.append(index)
        # Condition 2
        elif prev_item is not None and item is None:
            current_range.append(index - 1) # Close current range at the previous index
            all_ranges.append(current_range) # Add to all_ranges
            current_range = [] # Reset current_range

        prev_item = item
    # If current_range isn't closed, close it at the last index of the list
    if current_range:
        current_range.append(index)
        all_ranges.append(current_range)
    return all_ranges

Calling this function with your test cases gives the expected output:

[[1, 1]]
[[0, 1]]
[[2, 2]]
[[0, 1], [3, 4], [7, 7], [9, 9]]

Answer 4

Well, we can solve this by using classic sliding window approach.

Here is the solution which works fine:

def getRanges(nums):
    left = right = 0
    ranges, n = [], len(nums)
    while right < n:
        while left < n and nums[left] == None:
            left += 1
            right += 1
        while right < n and nums[right] != None:
            right += 1
        if right >= n:
            break
        ranges.append([left, right - 1])
        left = right = right + 1
    return ranges + [[left, right - 1]] if right - 1 >= left else ranges

Lets test it:

test = [
    [1, 0, None, 0, 0, None, None, 1, None, 0],
    [None, None, 3],
    [2, 1, None],
    [None, 0, None],
]

for i in test:
    print(getRanges(i))

Output:

[[0, 1], [3, 4], [7, 7], [9, 9]]
[[2, 2]]
[[0, 1]]
[[1, 1]]

Answer 5

Give it a try. Code uses Type Hint and a named tuple in order to increase readablity.

from typing import NamedTuple,List,Any

class Range(NamedTuple):
    left: int
    right: int
    
def get_ranges(lst: List[Any]) -> List[Range]:
    ranges : List[Range] = []
    left = None
    right = None
    for i,x in enumerate(lst):
        is_none = x is None
        if is_none:
            if left is not None :
                right = right if right is not None else left
                ranges.append(Range(left,right))
                left = None
                right = None
        else:
            if left is None:
                left = i
            else:
                right = i
    if left is not None:
        right = right if right is not None else left
        ranges.append(Range(left,right))
    return ranges


data = [[1,0,None,0,0,None,None,1,None,0],[None,None,3],[2,1,None],[None, 0, None]]
for entry in data:
    print(get_ranges(entry))

outut

[Range(left=0, right=1), Range(left=3, right=4), Range(left=7, right=7), Range(left=9, right=9)]
[Range(left=2, right=2)]
[Range(left=0, right=1)]
[Range(left=1, right=1)]

Answer 6

Here's my example. It is definitely NOT the most efficient way, but I think it is more intuitive and you can optimize it later.

def get_not_None_ranges(list_: list):
    res = []

    start_index = -1
    for i in range(len(list_)):
        e = list_[i]
        if e is not None:
            if start_index < 0:
                start_index = i
        else:
            if start_index >= 0:
                res.append([start_index, i - 1])
                start_index = -1

    if start_index >= 0:
        res.append([start_index, len(list_) - 1])
    return res

The main thought of this function:

1. start_index is initialized with -1
2. When we meet not None element, set start_index to its index
3. When we meet None, save [start_index, i - 1 (since the previous element is the end of the session)]. Then set start_index back to -1.
4. When we meet None but start_index is -1, we need to do nothing since we have not met the not None element this turn. For the same reason, do nothing when we meet not None when start_index > 0.
5. When the loop end but start_index still larger than 0, it means we haven't record this valid turn. So we need to do that manually.

I think it may be a little bit complex, it may help to paste the code above and debug it line by line in a debugger.