Check if Numbers Are Ascending in a Sentence

Easy

#1859Time: O(N), where N is the length of the string `s`. The `split()` operation takes O(N) time. The single loop through the tokens also takes O(N) time in total.Space: O(N). Although we are not storing the list of numbers anymore (O(1) for variables), the `split()` method still creates an array of tokens which requires O(N) space in the worst case.

Data structures

String

Prompt

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, or false otherwise.

Example 1:

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:

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

Example 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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach improves on the previous one by avoiding the need to store all numbers in a list. It still splits the sentence into tokens, but it processes them in a single pass, keeping track of only the most recently seen number to perform the check on the fly.

Algorithm

Split the input string s by spaces to get an array of tokens.
Initialize an integer variable previousNumber to -1.
Iterate through each token in the tokens array.
If the first character of the token is a digit:
- Parse the token into an integer currentNumber.
- If currentNumber <= previousNumber, return false.
- Update previousNumber = currentNumber.
If the loop completes, return true.

Walkthrough

Similar to the first approach, we start by splitting the input string s into tokens. We initialize a variable, previousNumber, to a value that is guaranteed to be smaller than any number in the sentence (e.g., -1, since all numbers are positive). We then iterate through the tokens one by one. For each token, we check if it's a number. If it is, we parse it into an integer, currentNumber. We then immediately compare currentNumber with previousNumber. If currentNumber is less than or equal to previousNumber, we have found a violation of the strictly increasing rule, so we can return false right away. Otherwise, we update previousNumber to be currentNumber and continue to the next token. If we process all tokens without returning false, it means the condition holds for all numbers, and we return true at the end.

1class Solution {2    public boolean areNumbersAscending(String s) {3        String[] tokens = s.split(" ");4        int previousNumber = -1;5 6        for (String token : tokens) {7            if (Character.isDigit(token.charAt(0))) {8                int currentNumber = Integer.parseInt(token);9                if (currentNumber <= previousNumber) {10                    return false;11                }12                previousNumber = currentNumber;13            }14        }15 16        return true;17    }18}

Complexity

Time

O(N), where N is the length of the string `s`. The `split()` operation takes O(N) time. The single loop through the tokens also takes O(N) time in total.

Space

O(N). Although we are not storing the list of numbers anymore (O(1) for variables), the `split()` method still creates an array of tokens which requires O(N) space in the worst case.

Trade-offs

Pros

More space-efficient than the first approach as it doesn't need a separate list for numbers.
Can terminate early as soon as a condition is violated.

Cons

Still uses O(N) auxiliary space due to the split() operation.

This approach involves two main steps. First, we parse the entire input sentence to identify and extract all the numbers, storing them in a separate list. Second, we iterate through this list of numbers to check if they are in strictly increasing order.

Algorithm

Split the input string s by spaces to get an array of tokens.
Create an empty integer list numbers.
Iterate through each token in the tokens array.
If the first character of the token is a digit, parse the token into an integer and add it to the numbers list.
Iterate through the numbers list from the second element (i = 1).
For each element numbers[i], compare it with the previous element numbers[i-1].
If numbers[i] <= numbers[i-1], return false.
If the loop completes, return true.

Walkthrough

The algorithm begins by splitting the input string s into an array of tokens using the space character as a delimiter. It then iterates through each token. For each token, it checks if it represents a number. A simple way to do this is to check if the first character of the token is a digit. If a token is identified as a number, it's converted from a string to an integer and added to a list, say numbers. After processing all tokens and populating the numbers list, the algorithm checks if this list is strictly sorted. It does this by iterating from the second element and comparing each number with its predecessor. If at any point a number is found to be less than or equal to the previous one (numbers.get(i) <= numbers.get(i - 1)), it immediately returns false. If the entire list is traversed without finding any violation, it means the numbers are strictly increasing, and the function returns true.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public boolean areNumbersAscending(String s) {6        String[] tokens = s.split(" ");7        List<Integer> numbers = new ArrayList<>();8 9        for (String token : tokens) {10            if (Character.isDigit(token.charAt(0))) {11                numbers.add(Integer.parseInt(token));12            }13        }14 15        for (int i = 1; i < numbers.size(); i++) {16            if (numbers.get(i) <= numbers.get(i - 1)) {17                return false;18            }19        }20 21        return true;22    }23}

Complexity

Time

O(N), where N is the length of the string `s`. Splitting the string takes O(N). Iterating through tokens and parsing also takes O(N) in total. The final check on the list of numbers takes O(K), where K is the number of numbers in the sentence (K <= N). Thus, the overall complexity is dominated by O(N).

Space

O(N), where N is the length of the string `s`. The `split()` method creates an array of tokens, which can take up to O(N) space. Additionally, the `numbers` list stores all the numbers, taking O(K) space where K is the number of numbers. The total space is O(N).

Trade-offs

Pros

Simple and easy to understand.
Separates the logic of parsing and checking, which can make the code cleaner.

Cons

Inefficient in terms of space. It requires extra space to store both the tokens and the extracted numbers.
It performs two separate passes over the data (one to extract numbers, one to check them).

This is the most optimal approach. It avoids splitting the string into an array of tokens, thereby eliminating the major source of auxiliary space usage. Instead, it iterates through the string character by character, parsing numbers and performing checks in a single pass.

Algorithm

Initialize an integer variable previousNumber to -1.
Initialize an index i = 0.
Loop while i is less than the length of s.
If s.charAt(i) is a digit:
- Initialize currentNumber = 0.
- While i is within bounds and s.charAt(i) is a digit:
  - currentNumber = currentNumber * 10 + (s.charAt(i) - '0').
  - Increment i.
- If currentNumber <= previousNumber, return false.
- Update previousNumber = currentNumber.
Else (if s.charAt(i) is not a digit):
- Increment i.
If the loop completes, return true.

Walkthrough

This method processes the string s directly without any preliminary splitting. It uses a pointer or index to traverse the string from left to right. A variable previousNumber is initialized to -1. The loop iterates through the string. When it encounters a digit, it knows a number token has started. It then enters a nested loop to parse the complete number by consuming all subsequent digits. Once a number (currentNumber) is fully parsed, it's compared with previousNumber. If currentNumber <= previousNumber, the function returns false. Otherwise, previousNumber is updated to currentNumber. If the character encountered is not a digit (i.e., a letter or a space), it's simply skipped, and the main loop continues to the next character. This process continues until the entire string is scanned. If the loop finishes, it means all numbers were strictly increasing, and true is returned.

1class Solution {2    public boolean areNumbersAscending(String s) {3        int previousNumber = -1;4        int i = 0;5        while (i < s.length()) {6            if (Character.isDigit(s.charAt(i))) {7                int currentNumber = 0;8                while (i < s.length() && Character.isDigit(s.charAt(i))) {9                    currentNumber = currentNumber * 10 + (s.charAt(i) - '0');10                    i++;11                }12                if (currentNumber <= previousNumber) {13                    return false;14                }15                previousNumber = currentNumber;16            } else {17                i++;18            }19        }20        return true;21    }22}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string with a single pointer, processing each character a constant number of times.

Space

O(1). This approach uses only a few variables to keep track of the state (`previousNumber`, `currentNumber`, `i`), regardless of the input string size. No auxiliary data structures that scale with the input size are used.

Trade-offs

Pros

Highly efficient in terms of space (O(1)).
Efficient in time (O(N)) with a single pass.
Avoids the overhead of creating intermediate data structures like arrays of strings.

Cons

The logic for manually parsing tokens can be slightly more complex to write and read compared to using built-in split functions.

Solutions

Solution

1class Solution {2public3  boolean areNumbersAscending(String s) {4    int pre = 0;5    for (var t : s.split(" ")) {6      if (t.charAt(0) <= '9') {7        int cur = Integer.parseInt(t);8        if (pre >= cur) {9          return false;10        }11        pre = cur;12      }13    }14    return true;15  }16}

1class Solution {2public:3  bool areNumbersAscending(string s) {4    int pre = 0;5    istringstream is(s);6    string t;7    while (is >> t) {8      if (isdigit(t[0])) {9        int cur = stoi(t);10        if (pre >= cur) {11          return false;12        }13        pre = cur;14      }15    }16    return true;17  }18};

1class Solution:2    def areNumbersAscending(self, s: str) -> bool: pre = 0 for t in s . split(): if t[0]. isdigit(): if (cur: = int(t)) <= pre: return False pre = cur return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  boolean areNumbersAscending(String s) {4    int pre = 0;5    for (var t : s.split(" ")) {6      if (t.charAt(0) <= '9') {7        int cur = Integer.parseInt(t);8        if (pre >= cur) {9          return false;10        }11        pre = cur;12      }13    }14    return true;15  }16}

1class Solution {2public:3  bool areNumbersAscending(string s) {4    int pre = 0;5    istringstream is(s);6    string t;7    while (is >> t) {8      if (isdigit(t[0])) {9        int cur = stoi(t);10        if (pre >= cur) {11          return false;12        }13        pre = cur;14      }15    }16    return true;17  }18};

1class Solution:2    def areNumbersAscending(self, s: str) -> bool: pre = 0 for t in s . split(): if t[0]. isdigit(): if (cur: = int(t)) <= pre: return False pre = cur return True

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.