Welcome to Subscribe On Youtube

975. Odd Even Jump

Description

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1^st, 3^rd, 5^th, ...) jumps in the series are called odd-numbered jumps, and the (2^nd, 4^th, 6^th, ...) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

• During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
• During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
• It may be the case that for some index i, there are no legal jumps.

A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

 

Example 1:

Input: arr = [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.

Example 2:

Input: arr = [2,3,1,1,4]
Output: 3
Explanation: 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0].
During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3
During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2].
We can't jump from i = 3 to i = 4, so the starting index i = 0 is not good.
In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can't jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some
number of jumps.

Example 3:

Input: arr = [5,1,3,4,2]
Output: 3
Explanation: We can reach the end from starting indices 1, 2, and 4.

 

Constraints:

• 1 <= arr.length <= 2 * 104
• 0 <= arr[i] < 105

Solutions

Solution 2: Ordered Set + Dynamic Programming

Thinking

An odd jump goes to the smallest value on the right that is at least the current one; an even jump goes to the largest that is at most the current. $n$ can reach $2 \times 10^4$. When every value is equal, each jump lands on the next index, so the call chain is as long as $n$ and exceeds the default recursion limit.

Walking from right to left, the ordered map holds only indexes farther to the right, so $g[i][0/1]$ is either a larger index or $-1$.

Reachability depends only on $(i,\text{parity})$ and only on a position to the right. Let $f[i][k]$ mean a jump of parity $k$ from $i$ can reach the end. Both cells of $f[n-1]$ are true. $i$ runs from $n-2$ down to $0$, and a real successor copies the opposite parity at that successor. The answer counts the true cells $f[i][1]$.

We first use an ordered set to preprocess the positions that can be jumped to from each position, recorded in array $g$, where $g[i][1]$ and $g[i][0]$ represent the positions that can be jumped to when the current position is an odd jump or an even jump, respectively. If no position can be jumped to, then both $g[i][1]$ and $g[i][0]$ are $-1$. The map stores only indexes to the right, so $g[i][k]$ is either $-1$ or strictly greater than $i$.

Let $f[i][k]$ mean that, starting at index $i$ with the next jump of parity $k$, we can reach the end of the array. Both $f[n-1][0]$ and $f[n-1][1]$ are true. For $i$ from $n-2$ down to $0$, if $g[i][k] \neq -1$, then $f[i][k] = f[g[i][k]][k \oplus 1]$; otherwise $f[i][k]$ is false. The state on the right is already known when it is read.

The answer is the number of indexes $i$ for which $f[i][1]$ is true.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array.

• Java
• C++
• Python
• Go
• Rust

• class Solution {
      private int n;
      private Integer[][] f;
      private int[][] g;
  
      public int oddEvenJumps(int[] arr) {
          TreeMap<Integer, Integer> tm = new TreeMap<>();
          n = arr.length;
          f = new Integer[n][2];
          g = new int[n][2];
          for (int i = n - 1; i >= 0; --i) {
              var hi = tm.ceilingEntry(arr[i]);
              g[i][1] = hi == null ? -1 : hi.getValue();
              var lo = tm.floorEntry(arr[i]);
              g[i][0] = lo == null ? -1 : lo.getValue();
              tm.put(arr[i], i);
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              ans += dfs(i, 1);
          }
          return ans;
      }
  
      private int dfs(int i, int k) {
          if (i == n - 1) {
              return 1;
          }
          if (g[i][k] == -1) {
              return 0;
          }
          if (f[i][k] != null) {
              return f[i][k];
          }
          return f[i][k] = dfs(g[i][k], k ^ 1);
      }
  }
  
  
  // Solution 2
  class Solution {
      public int oddEvenJumps(int[] arr) {
          TreeMap<Integer, Integer> tm = new TreeMap<>();
          int n = arr.length;
          int[][] g = new int[n][2];
          for (int i = n - 1; i >= 0; --i) {
              var hi = tm.ceilingEntry(arr[i]);
              g[i][1] = hi == null ? -1 : hi.getValue();
              var lo = tm.floorEntry(arr[i]);
              g[i][0] = lo == null ? -1 : lo.getValue();
              tm.put(arr[i], i);
          }
          boolean[][] f = new boolean[n][2];
          f[n - 1][0] = f[n - 1][1] = true;
          for (int i = n - 2; i >= 0; --i) {
              for (int k = 0; k < 2; ++k) {
                  int j = g[i][k];
                  if (j != -1) {
                      f[i][k] = f[j][k ^ 1];
                  }
              }
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              if (f[i][1]) {
                  ++ans;
              }
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      int oddEvenJumps(vector<int>& arr) {
          int n = arr.size();
          map<int, int> d;
          int f[n][2];
          int g[n][2];
          memset(f, 0, sizeof(f));
          for (int i = n - 1; ~i; --i) {
              auto it = d.lower_bound(arr[i]);
              g[i][1] = it == d.end() ? -1 : it->second;
              it = d.upper_bound(arr[i]);
              g[i][0] = it == d.begin() ? -1 : prev(it)->second;
              d[arr[i]] = i;
          }
          function<int(int, int)> dfs = [&](int i, int k) -> int {
              if (i == n - 1) {
                  return 1;
              }
              if (g[i][k] == -1) {
                  return 0;
              }
              if (f[i][k] != 0) {
                  return f[i][k];
              }
              return f[i][k] = dfs(g[i][k], k ^ 1);
          };
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              ans += dfs(i, 1);
          }
          return ans;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      int oddEvenJumps(vector<int>& arr) {
          int n = arr.size();
          map<int, int> d;
          int g[n][2];
          for (int i = n - 1; ~i; --i) {
              auto it = d.lower_bound(arr[i]);
              g[i][1] = it == d.end() ? -1 : it->second;
              it = d.upper_bound(arr[i]);
              g[i][0] = it == d.begin() ? -1 : prev(it)->second;
              d[arr[i]] = i;
          }
          int f[n][2];
          memset(f, 0, sizeof(f));
          f[n - 1][0] = f[n - 1][1] = 1;
          for (int i = n - 2; ~i; --i) {
              for (int k = 0; k < 2; ++k) {
                  int j = g[i][k];
                  if (j != -1) {
                      f[i][k] = f[j][k ^ 1];
                  }
              }
          }
          int ans = 0;
          for (int i = 0; i < n; ++i) {
              ans += f[i][1];
          }
          return ans;
      }
  };
  
  

• from sortedcontainers import SortedDict
  
  
  class Solution:
      def oddEvenJumps(self, arr: List[int]) -> int:
          @cache
          def dfs(i: int, k: int) -> bool:
              if i == n - 1:
                  return True
              if g[i][k] == -1:
                  return False
              return dfs(g[i][k], k ^ 1)
  
          n = len(arr)
          g = [[0] * 2 for _ in range(n)]
          sd = SortedDict()
          for i in range(n - 1, -1, -1):
              j = sd.bisect_left(arr[i])
              g[i][1] = sd.values()[j] if j < len(sd) else -1
              j = sd.bisect_right(arr[i]) - 1
              g[i][0] = sd.values()[j] if j >= 0 else -1
              sd[arr[i]] = i
          return sum(dfs(i, 1) for i in range(n))
  
  
  
  # Solution 2
  class Solution:
      def oddEvenJumps(self, arr: List[int]) -> int:
          n = len(arr)
          g = [[-1] * 2 for _ in range(n)]
          sd = SortedDict()
          for i in range(n - 1, -1, -1):
              j = sd.bisect_left(arr[i])
              g[i][1] = sd.values()[j] if j < len(sd) else -1
              j = sd.bisect_right(arr[i]) - 1
              g[i][0] = sd.values()[j] if j >= 0 else -1
              sd[arr[i]] = i
          f = [[False] * 2 for _ in range(n)]
          f[-1][0] = f[-1][1] = True
          for i in range(n - 2, -1, -1):
              for k in range(2):
                  j = g[i][k]
                  if j != -1:
                      f[i][k] = f[j][k ^ 1]
          return sum(f[i][1] for i in range(n))
  
  

• func oddEvenJumps(arr []int) (ans int) {
  	n := len(arr)
  	rbt := redblacktree.NewWithIntComparator()
  	f := make([][2]int, n)
  	g := make([][2]int, n)
  	for i := n - 1; i >= 0; i-- {
  		if v, ok := rbt.Ceiling(arr[i]); ok {
  			g[i][1] = v.Value.(int)
  		} else {
  			g[i][1] = -1
  		}
  		if v, ok := rbt.Floor(arr[i]); ok {
  			g[i][0] = v.Value.(int)
  		} else {
  			g[i][0] = -1
  		}
  		rbt.Put(arr[i], i)
  	}
  	var dfs func(int, int) int
  	dfs = func(i, k int) int {
  		if i == n-1 {
  			return 1
  		}
  		if g[i][k] == -1 {
  			return 0
  		}
  		if f[i][k] != 0 {
  			return f[i][k]
  		}
  		f[i][k] = dfs(g[i][k], k^1)
  		return f[i][k]
  	}
  	for i := 0; i < n; i++ {
  		if dfs(i, 1) == 1 {
  			ans++
  		}
  	}
  	return
  }
  
  
  // Solution 2
  func oddEvenJumps(arr []int) (ans int) {
  	n := len(arr)
  	rbt := redblacktree.NewWithIntComparator()
  	g := make([][2]int, n)
  	for i := n - 1; i >= 0; i-- {
  		if v, ok := rbt.Ceiling(arr[i]); ok {
  			g[i][1] = v.Value.(int)
  		} else {
  			g[i][1] = -1
  		}
  		if v, ok := rbt.Floor(arr[i]); ok {
  			g[i][0] = v.Value.(int)
  		} else {
  			g[i][0] = -1
  		}
  		rbt.Put(arr[i], i)
  	}
  	f := make([][2]bool, n)
  	f[n-1][0], f[n-1][1] = true, true
  	for i := n - 2; i >= 0; i-- {
  		for k := 0; k < 2; k++ {
  			j := g[i][k]
  			if j != -1 {
  				f[i][k] = f[j][k^1]
  			}
  		}
  	}
  	for i := 0; i < n; i++ {
  		if f[i][1] {
  			ans++
  		}
  	}
  	return
  }
  
  

• use std::collections::BTreeMap;
  
  impl Solution {
      pub fn odd_even_jumps(arr: Vec<i32>) -> i32 {
          let n: usize = arr.len();
          let mut f: Vec<Vec<Option<i32>>> = vec![vec![None; 2]; n];
          let mut g: Vec<Vec<i32>> = vec![vec![-1; 2]; n];
          let mut tm: BTreeMap<i32, usize> = BTreeMap::new();
  
          for i in (0..n).rev() {
              if let Some((_, &v)) = tm.range(arr[i]..).next() {
                  g[i][1] = v as i32;
              }
              if let Some((_, &v)) = tm.range(..=arr[i]).next_back() {
                  g[i][0] = v as i32;
              }
              tm.insert(arr[i], i);
          }
  
          fn dfs(
              i: usize,
              k: usize,
              n: usize,
              f: &mut Vec<Vec<Option<i32>>>,
              g: &Vec<Vec<i32>>,
          ) -> i32 {
              if i == n - 1 {
                  return 1;
              }
              if g[i][k] == -1 {
                  return 0;
              }
              if let Some(v) = f[i][k] {
                  return v;
              }
              let res = dfs(g[i][k] as usize, k ^ 1, n, f, g);
              f[i][k] = Some(res);
              res
          }
  
          let mut ans: i32 = 0;
          for i in 0..n {
              ans += dfs(i, 1, n, &mut f, &g);
          }
          ans
      }
  }
  
  
  
  // Solution 2
  use std::collections::BTreeMap;
  
  impl Solution {
      pub fn odd_even_jumps(arr: Vec<i32>) -> i32 {
          let n = arr.len();
          let mut g = vec![[-1, -1]; n];
          let mut tm: BTreeMap<i32, usize> = BTreeMap::new();
  
          for i in (0..n).rev() {
              if let Some((_, &v)) = tm.range(arr[i]..).next() {
                  g[i][1] = v as i32;
              }
              if let Some((_, &v)) = tm.range(..=arr[i]).next_back() {
                  g[i][0] = v as i32;
              }
              tm.insert(arr[i], i);
          }
  
          let mut f = vec![[false, false]; n];
          f[n - 1] = [true, true];
          for i in (0..n - 1).rev() {
              for k in 0..2 {
                  let j = g[i][k];
                  if j != -1 {
                      f[i][k] = f[j as usize][k ^ 1];
                  }
              }
          }
  
          f.iter().filter(|row| row[1]).count() as i32
      }
  }
  
  

All Problems

All Solutions