Problem

A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.

  • For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.

Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).

Return true if so, orfalse otherwise.

Examples

Example 1

1
2
3
4

Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

Example 2

1
2
3

Input: s = "hello world 5 x 5"
Output: false
Explanation: The numbers in s are: _**5**_ , **_5_**. They are not strictly increasing.

Example 3

1
2
3

Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
Output: false
Explanation: The numbers in s are: 7, _**51**_ , _**50**_ , 60. They are not strictly increasing.

Constraints

  • 3 <= s.length <= 200
  • s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.
  • The number of tokens in s is between 2 and 100, inclusive.
  • The tokens in s are separated by a single space.
  • There are at least two numbers in s.
  • Each number in s is a positive number less than 100, with no leading zeros.
  • s contains no leading or trailing spaces.

Solution

Method 1 – Single Pass with Previous Number Tracking

Intuition

We need to extract all numbers from the sentence and check if they are strictly increasing. This can be done efficiently by scanning the sentence token by token and comparing each number to the previous one.

Reasoning

By iterating through each token, we can identify numbers and compare each to the last seen number. If any number is not greater than the previous, the sequence is not strictly increasing.

Approach

  1. Split the sentence into tokens by spaces.
  2. Initialize a variable to keep track of the previous number (start with -1).
  3. For each token:
    • If the token is a number (all digits), convert it to an integer.
    • Compare it to the previous number. If it is not strictly greater, return false.
    • Update the previous number.
  4. If all numbers are strictly increasing, return true.

Edge cases:

  • Sentences with only two numbers.
  • Numbers at the start or end of the sentence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool areNumbersAscending(string s) {
        int prev = -1;
        stringstream ss(s);
        string token;
        while (ss >> token) {
            if (all_of(token.begin(), token.end(), ::isdigit)) {
                int num = stoi(token);
                if (num <= prev) return false;
                prev = num;
            }
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func areNumbersAscending(s string) bool {
    prev := -1
    for _, token := range strings.Split(s, " ") {
        if n, err := strconv.Atoi(token); err == nil {
            if n <= prev {
                return false
            }
            prev = n
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public boolean areNumbersAscending(String s) {
        int prev = -1;
        for (String token : s.split(" ")) {
            if (token.chars().allMatch(Character::isDigit)) {
                int num = Integer.parseInt(token);
                if (num <= prev) return false;
                prev = num;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun areNumbersAscending(s: String): Boolean {
        var prev = -1
        for (token in s.split(" ")) {
            if (token.all { it.isDigit() }) {
                val num = token.toInt()
                if (num <= prev) return false
                prev = num
            }
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def are_numbers_ascending(self, s: str) -> bool:
        prev = -1
        for token in s.split():
            if token.isdigit():
                num = int(token)
                if num <= prev:
                    return False
                prev = num
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn are_numbers_ascending(s: String) -> bool {
        let mut prev = -1;
        for token in s.split_whitespace() {
            if let Ok(num) = token.parse::<i32>() {
                if num <= prev {
                    return false;
                }
                prev = num;
            }
        }
        true
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan the sentence once and process each token in constant time.
  • 🧺 Space complexity: O(1), as we use only a few variables for tracking numbers.