LeetCode 2042 - Check if Numbers Are Ascending in a Sentence

LeetCode Problem 2042

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to analyze a sentence represented as a string s and determine whether all numbers embedded in the sentence are strictly increasing from left to right. A sentence here is defined as a sequence of tokens separated by single spaces, where each token is either a word of lowercase English letters or a positive integer without leading zeros. The challenge is to ignore the words and only consider the numeric tokens in order.

The input string s will have a length between 3 and 200 characters and contain at least two numbers. Each number is less than 100, so it fits in a small integer range. The task is to return true if each number is strictly smaller than the next number that appears, otherwise false.

Important edge cases include sentences where numbers are repeated, numbers decrease, numbers appear at the beginning or end, and numbers are not consecutive in terms of token positions. For example, "a 1 b 2" is valid, while "a 2 b 1" is not.

Approaches

The brute-force approach is simple: split the sentence into tokens, iterate through each token, and whenever a token is numeric, convert it to an integer and append it to a list. After extracting all numbers, iterate through the list to check if each number is strictly less than the next number. This works correctly but requires two passes: one to extract numbers and another to check the ordering.

The optimal approach combines these two steps into a single pass. Instead of storing all numbers, we maintain a single variable prev to track the previous number seen. While iterating over the tokens, if a token is numeric, we compare it with prev. If it is not greater than prev, we immediately return false. Otherwise, we update prev and continue. This reduces space complexity and slightly improves efficiency because we can terminate early if an order violation is detected.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(m)	Extract numbers in one pass, check strictly increasing in second pass; n is number of tokens, m is number of numbers
Optimal	O(n)	O(1)	Single-pass solution using a previous number variable; n is number of tokens

Algorithm Walkthrough

1. Initialize a variable prev to 0 to track the last seen number. Zero is safe because all numbers are positive.
2. Split the input string s by spaces to get individual tokens.
3. Iterate through each token in the sentence.
4. For each token, check if it is a number using the .isdigit() method.
5. If the token is a number, convert it to an integer num.
6. Compare num with prev. If num <= prev, return false immediately since the sequence is not strictly increasing.
7. Otherwise, update prev = num and continue iterating.
8. After the iteration completes without returning false, return true.

Why it works: At each step, prev maintains the invariant that it holds the last number seen in the sentence. Any violation of strict increasing order is detected immediately. This guarantees correctness without needing to store all numbers.

Python Solution

class Solution:
    def areNumbersAscending(self, s: str) -> bool:
        prev = 0
        tokens = s.split()
        
        for token in tokens:
            if token.isdigit():
                num = int(token)
                if num <= prev:
                    return False
                prev = num
                
        return True

In the Python implementation, we first initialize prev to 0 and split the sentence into tokens. The loop iterates over each token, checking if it consists only of digits. If it is a number, we convert it to an integer and compare it with the previous number. If the sequence is violated, we immediately return false. Otherwise, we update prev and continue. The function returns true if all numbers satisfy the strictly increasing condition.

Go Solution

import (
    "strconv"
    "strings"
)

func areNumbersAscending(s string) bool {
    prev := 0
    tokens := strings.Split(s, " ")
    
    for _, token := range tokens {
        if num, err := strconv.Atoi(token); err == nil {
            if num <= prev {
                return false
            }
            prev = num
        }
    }
    
    return true
}

In Go, the implementation follows the same logic. We split the sentence into tokens and use strconv.Atoi to attempt conversion. If the conversion succeeds (err == nil), the token is numeric. The number is compared against prev, and the function returns false if it is not strictly greater. Otherwise, prev is updated.

Worked Examples

Example 1

Input: "1 box has 3 blue 4 red 6 green and 12 yellow marbles"

Token	Numeric?	Prev	Check
"1"	Yes	0	1 > 0 → update prev = 1
"box"	No	1	-
"has"	No	1	-
"3"	Yes	1	3 > 1 → update prev = 3
"blue"	No	3	-
"4"	Yes	3	4 > 3 → update prev = 4
"red"	No	4	-
"6"	Yes	4	6 > 4 → update prev = 6
"green"	No	6	-
"and"	No	6	-
"12"	Yes	6	12 > 6 → update prev = 12
"yellow"	No	12	-
"marbles"	No	12	-

Return true.

Example 2

Input: "hello world 5 x 5"

Token	Numeric?	Prev	Check
"hello"	No	0	-
"world"	No	0	-
"5"	Yes	0	5 > 0 → prev = 5
"x"	No	5	-
"5"	Yes	5	5 ≤ 5 → return false

Return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We split and iterate over each token once; n is number of tokens
Space	O(n)	Token splitting creates a list of size proportional to n

The time complexity is linear in the number of tokens because we visit each token once. Space complexity is linear due to the token list created by split. No additional data structures are needed beyond a single integer variable for tracking.

Test Cases

# provided examples
assert Solution().areNumbersAscending("1 box has 3 blue 4 red 6 green and 12 yellow marbles") == True
assert Solution().areNumbersAscending("hello world 5 x 5") == False
assert Solution().areNumbersAscending("sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s") == False

# boundary tests
assert Solution().areNumbersAscending("1 2") == True  # minimal numbers, strictly increasing
assert Solution().areNumbersAscending("99 100") == True  # upper boundary
assert Solution().areNumbersAscending("2 1") == False  # descending
assert Solution().areNumbersAscending("1 1") == False  # equal numbers
assert Solution().areNumbersAscending("a 1 b 2 c 3") == True  # words in between numbers

Test	Why
"1 box has 3 blue 4 red 6 green and 12 yellow marbles"	Standard case with multiple numbers increasing
"hello world 5 x 5"	Numbers repeated → should return false
"sunset is at 7 51 ... 60 s"	Numbers not strictly increasing → return false
"1 2"	Minimal valid sequence
"99 100"	Upper boundary values
"2 1"	Descending numbers
"1 1"	Equal numbers
"a 1 b 2 c 3"	Words interleaved with numbers

Edge Cases

The first edge case is when numbers appear at the start or end of the sentence, e.g., "1 apple and 2 oranges". The solution handles this naturally since it checks all numeric tokens regardless of position.

A second edge case is when numbers are equal or decrease, which violates the strictly increasing condition. Examples like "5 5" or "3 2" are handled correctly because the comparison num <= prev immediately returns false.

A third edge case is when numbers are interleaved with words, possibly with many words in between. For instance, "a 1 b 2 c 3" ensures the algorithm correctly ignores non-numeric tokens while maintaining the previous number state.

This solution is robust against all valid inputs defined in the problem constraints.