Check if Numbers Are Ascending in a Sentence

EASY

Description

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

Checkout 3 different approaches to solve Check if Numbers Are Ascending in a Sentence. Click on different approaches to view the approach and algorithm in detail.

Single Pass Using split()

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Check if Numbers Are Ascending in a Sentence. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Check if Numbers Are Ascending in a Sentence

Data Structures:

String