count-valid-suffix-sorts-i

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given two integer arrays <code>nums</code> and <code>target</code>, both of length <code>n</code>.

For each index <code>i</code>, consider sorting the suffix <code>nums[i..n - 1]</code> of the original array in non-increasing order.

Return the number of indices <code>i</code> for which the resulting array is equal to <code>target</code>.

A subarray is a contiguous non-empty sequence of elements within an array.

A suffix of an array is a subarray that begins at any index and extends to the end of the array.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,2,3], target = [3,2,1]

Output: 1

Explanation:

<ul>
	<li><code>i = 0</code>: The resulting array is <code>[3, 2, 1]</code>, which equals <code>target</code>.</li>
	<li><code>i = 1</code>: The resulting array is <code>[1, 3, 2]</code>.</li>
	<li><code>i = 2</code>: The resulting array is <code>[1, 2, 3]</code>.</li>
</ul>

Only <code>i = 0</code> is valid, so the answer is 1.
</div>

Example 2:

<div class="example-block">
Input: nums = [1,5,6,4,6], target = [1,5,6,6,4]

Output: 2

Explanation:

Choosing either <code>i = 2</code> or <code>i = 3</code> results in <code>[1, 5, 6, 6, 4]</code>. No other index produces <code>target</code>. Therefore, the answer is 2.
</div>

Example 3:

<div class="example-block">
Input: nums = [7,6,8], target = [8,6,7]

Output: 0

Explanation:

Sorting the suffix starting at indices 0, 1, and 2 produces <code>[8, 7, 6]</code>, <code>[7, 8, 6]</code>, and <code>[7, 6, 8]</code>, respectively. None equals <code>target</code>, so the answer is 0.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == nums.length == target.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i], target[i] &lt;= 10​​​​​​​5</code>​​​​​​​​​​​​​​</li>
</ul>

Weekly Contest 527

weekly-contest-527

countSuffix

Count Valid Suffix Sorts I

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

You are given two integer arrays nums and target, both of length n.

For each index i, consider sorting the suffix nums[i..n - 1] of the original array in non-increasing order.

Return the number of indices i for which the resulting array is equal to target.

A subarray is a contiguous non-empty sequence of elements within an array.

A suffix of an array is a subarray that begins at any index and extends to the end of the array.

 

Example 1:

Input: nums = [1,2,3], target = [3,2,1]

Output: 1

Explanation:

 * i = 0: The resulting array is [3, 2, 1], which equals target.
 * i = 1: The resulting array is [1, 3, 2].
 * i = 2: The resulting array is [1, 2, 3].

Only i = 0 is valid, so the answer is 1.

Example 2:

Input: nums = [1,5,6,4,6], target = [1,5,6,6,4]

Output: 2

Explanation:

Choosing either i = 2 or i = 3 results in [1, 5, 6, 6, 4]. No other index produces target. Therefore, the answer is 2.

Example 3:

Input: nums = [7,6,8], target = [8,6,7]

Output: 0

Explanation:

Sorting the suffix starting at indices 0, 1, and 2 produces [8, 7, 6], [7, 8, 6], and [7, 6, 8], respectively. None equals target, so the answer is 0.

 

Constraints:

 * 1 <= n == nums.length == target.length <= 105
 * 1 <= nums[i], target[i] <= 10 5