Solve word path in grid and trapped water

You are given two independent programming tasks. --- ### Problem 1: Check if a word exists in a 2D character grid You are given a 2D grid `board` of characters with `m` rows and `n` columns, and a string `word`. You need to determine if `word` can be formed by sequentially adjacent cells in the grid. Adjacent cells are horizontally or vertically neighboring (no diagonals). The same cell **cannot** be used more than once in forming the word. Return `true` if the word exists in the grid, and `false` otherwise. **Example:** Input: - `board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]` - `word = "ABCCED"` Output: `true` Explanation: The word can be formed by the path `A -> B -> C -> C -> E -> D` using adjacent cells without reusing any cell. **Constraints (you may assume any reasonable values if not given):** - `1 <= m, n <= 10^2` - `1 <= len(word) <= m * n` - `board[i][j]` is an uppercase or lowercase English letter. Describe an algorithm to solve this problem and analyze its time and space complexity. --- ### Problem 2: Compute total water trapped between bars You are given an array `height` where each element `height[i]` represents the height of a vertical bar of width 1 at position `i`. After raining, water may be trapped between the bars. Compute how many units of water are trapped between the bars. Return the total amount of trapped water as an integer. **Example 1:** Input: - `height = [0,1,0,2,1,0,1,3,2,1,2,1]` Output: `6` Explanation: 6 units of water are trapped in the valleys formed by the bars. **Example 2:** Input: - `height = [4,2,0,3,2,5]` Output: `9` **Constraints (you may assume any reasonable values if not given):** - `1 <= height.length <= 2 * 10^5` - `0 <= height[i] <= 10^4` Design an efficient algorithm (both time and space) to compute the trapped water and analyze its complexity. An in-place or two-pointer solution is preferred in an interview setting.