FastPrep
Problem · Dynamic Programming

TikTok User

Learn this problem
● HardTiktok logoTiktokOA
See Tiktok hiring insights

Problem statement

A TikTok developer assigns integers to users in an array arr.

An arrangement is good if the absolute difference between every pair of adjacent values is at most 1. For example, [1, 2, 1] is good, but [2, 1, 3] is not because the difference between 1 and 3 is 2.

Some values are missing and are represented by arr[i] = 0. Count the ways to replace every missing value with an arbitrary integer so that the final array is good.

Because the number of ways can be large, return it modulo 10^9 + 7.

The input contains at least one known, nonzero value. A replacement value may itself be 0.

Function

tiktokUser(arr: int[]) → int

Examples

Example 1

arr = [0, 0, 1]return = 9

Working backward from the final value 1, the second position can be 0, 1, or 2. For each of those choices, the first position again has three valid choices. Therefore there are 3 × 3 = 9 good completions.

Constraints

  • 1 ≤ arr.length ≤ 10^5
  • -10^9 ≤ arr[i] ≤ 10
  • At least one element of arr is nonzero.
  • 0 denotes a missing value and may be replaced by any integer.

More Tiktok problems

drafts saved locally
public int tiktokUser(int[] arr) {
  // write your code here
}
arr[0, 0, 1]
expected9
checking account