# 3532. Path Existence Queries in a Graph I
[3532. Path Existence Queries in a Graph I](https://leetcode.com/problems/path-existence-queries-in-a-graph-i/) (<font color="#FFB800"> Medium</font> 通過率: 54.4%)

## 限制條件
<ul>
<li>1 <= n == nums.length <= 10^5</li>
<li>0 <= nums[i] <= 10^5</li>
<li>nums is sorted in non-decreasing order.</li>
<li>0 <= maxDiff <= 10^5</li>
<li>1 <= queries.length <= 10^5</li>
<li>queries[i] == [ui, vi]</li>
<li>0 <= ui, vi < n</li>
</ul>

### 解法 1
主要是去看中間有沒有超過限制(maxDiff)的線段，有的話就將那一個 query 回傳 false
那這個方法是最差的暴力解，但我會先寫一個暴力解，再往上去寫比較快的(因為我不熟)，這樣可以提高自己的理解力，也可以做為對照看有沒有寫錯。

- 時間複雜度: O(n*m)
- 空間複雜度: O(n)

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<bool> results(queries.size(), true);
        for (int i = 0; i < queries.size(); i++) {
            if (queries[i][0] == queries[i][1])
                continue;
            if (queries[i][0] > queries[i][1])
                swap(queries[i][0], queries[i][1]);
            for (int j = queries[i][0]; j < queries[i][1]; j++) {
                int fNum = nums[j];
                int bNum = nums[j + 1];
                cout << (bNum - fNum) << endl;
                if (abs(bNum - fNum) > maxDiff) {
                    results[i] = false;
                    break;
                }
            }
        }
        return results;
    }
};

### 解法 2
第二種算是預先把所有線段看過，因為在每一個 query 當中，只要遇到一個超過 Diff 的就要回傳 false ，因此我將每個相鄰線段都先判斷，並用 record 儲存狀態，再讓 query 用"相減" 的方式可以讓每一個 query 都是 O(1) 就可以解決問題

- 時間複雜度: O(M+N)
- 空間複雜度: O(M+N)

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<bool> results(queries.size(), true);
        vector<int> record(nums.size(), 0);
        for (int i = 1; i < n; i++) {
            int fNum = nums[i - 1];
            int bNum = nums[i];
            int r = (bNum - fNum) > maxDiff;
            record[i] = record[i - 1] + r;
        }
        for (int i = 0; i < queries.size(); i++) {
            int fIdx = queries[i][0];
            int bIdx = queries[i][1];
            int result = (record[bIdx] - record[fIdx]);
            results[i] = !result;
        }
        return results;
    }
};