CODEWITHSUNDEEP
mysqlsql
Duno
Duno

Reputation: 47

Find out the ranges of numbers that are monotonically increasing

I found this question on leetcode:

Given a table name "numbers" with 1 column name "id" like this: 2, 3, 5, 1, 4, 2, 7, 8 Write an SQL script to find out the ranges of numbers that are monotonically increasing. Answer: 2-5, 1-4, 2-8

My solution is what follows, which is quite long with a lot of subqueries since I'm new with SQL, I'm only comfortable with select, from, where, group by. Could you please let me know if my query is correct? I believe that there exists a simpler query than my solution, but for the moment I don't know how to do it. Could you please let me know how?

with x as
select current, increasing as a, lead(increasing,1,0) as b
from 
(
    (select current, (case when current > before then 1 else 0 end) as increasing
    from 
        (select id as current, lag(id,1,0) as before
         from table numbers)
     )
)

select t1.start, t2.end
(select current as start, ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
from x
where a=0 and b=1) t1
inner join 
(select current as end, ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
from x
where a=1 and b=0) t2
on t1.numrow = t2.numrow

Thanks.

Upvotes: 0

Views: 628

Answers (2)

Lukasz Szozda
Lukasz Szozda

Reputation: 175586

I believe that there exists a simpler query than my solution, but for the moment I don't know how to do it

This is gaps-and-islands class problem. Please note that tables are not sorted by design. You need some kind of column to determine index. ORDER BY (SELECT NULL) is probably to satisfy T-SQL but it is not safe.

There are multiple ways to solve it. One of my favourites is MATCH_RECOGNIZE:

SELECT f, l 
FROM t
MATCH_RECOGNIZE (
   ORDER BY id
   MEASURES first(c) AS f,
            last(c) AS l
   ONE ROW PER MATCH 
   PATTERN( l+ ge* )
   DEFINE l AS c < NEXT(c) OR NEXT(c) IS NULL,
          ge AS c >= NEXT(c) 
) mr;

db<>fiddle demo

Upvotes: 0

Gordon Linoff
Gordon Linoff

Reputation: 1269503

In order to answer your question, your data needs to have an ordering column. SQL tables represent unordered (multi)sets, so there is no ordering without such a column.

Use lag() to determine where a monotonically increasing group starts. Then do a cumulative sum to assign a grouping to the group. And finally aggregation:

select min(id), max(id)
from (select n.*,
             sum(case when prev_id < id then 0 else 1 end) over (order by <ordering col>) as grp
      from (select n.*,
                   lag(id) over (order by <ordering col>) as prev_n
            from numbers n
           ) n
     ) n
group by grp;

Here is a db<>fiddle.

Upvotes: 1

Related Questions