# Check if Numbers Are Ascending in a Sentence
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-numbers-are-ascending-in-a-sentence)
Canonical: https://scaleengineer.com/dsa/problems/check-if-numbers-are-ascending-in-a-sentence
**Data structures:** String
---
## 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, or_ `false` _otherwise_.

**Example 1:**

![example-1](https://assets.glich.co/dsa/check-if-numbers-are-ascending-in-a-sentence/image0.png) 

**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](https://assets.glich.co/dsa/check-if-numbers-are-ascending-in-a-sentence/image1.png) 

**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
## Extract All Numbers into a List
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.
**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).
**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).
### Explanation
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`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean areNumbersAscending(String s) {
        String[] tokens = s.split(" ");
        List<Integer> numbers = new ArrayList<>();

        for (String token : tokens) {
            if (Character.isDigit(token.charAt(0))) {
                numbers.add(Integer.parseInt(token));
            }
        }

        for (int i = 1; i < numbers.size(); i++) {
            if (numbers.get(i) <= numbers.get(i - 1)) {
                return false;
            }
        }

        return true;
    }
}
```
### 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`.

## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Single Pass with Manual Parsing (O(1) Space)
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public boolean areNumbersAscending(String s) {
        int previousNumber = -1;
        int i = 0;
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int currentNumber = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    currentNumber = currentNumber * 10 + (s.charAt(i) - '0');
                    i++;
                }
                if (currentNumber <= previousNumber) {
                    return false;
                }
                previousNumber = currentNumber;
            } else {
                i++;
            }
        }
        return true;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool areNumbersAscending(string s) {
    int pre = 0;
    istringstream is(s);
    string t;
    while (is >> t) {
      if (isdigit(t[0])) {
        int cur = stoi(t);
        if (pre >= cur) {
          return false;
        }
        pre = cur;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    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

```