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.