Scale Engineer

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:

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:

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.

class Solution {    public boolean areNumbersAscending(String s) {        String[] tokens = s.split(" ");        int previousNumber = -1;         for (String token : tokens) {            if (Character.isDigit(token.charAt(0))) {                int currentNumber = Integer.parseInt(token);                if (currentNumber <= previousNumber) {                    return false;                }                previousNumber = currentNumber;            }        }         return true;    }}

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.

Solutions

class Solution {public  boolean areNumbersAscending(String s) {    int pre = 0;    for (var t : s.split(" ")) {      if (t.charAt(0) <= '9') {        int cur = Integer.parseInt(t);        if (pre >= cur) {          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 →

Next problem