count-subarrays-with-k-distinct-integers

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

<p>You are given an integer array <code>nums</code> and two integers <code>k</code> and <code>m</code>.</p>

<p>Return an integer denoting the count of <strong><span data-keyword="subarray-nonempty">subarrays</span></strong> of <code>nums</code> such that:</p>

<ul>
	<li>The subarray contains <strong>exactly</strong> <code>k</code> <strong>distinct</strong> integers.</li>
	<li>Within the subarray, each <strong>distinct</strong> integer appears <strong>at least</strong> <code>m</code> times.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,1,2,2], k = 2, m = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>The possible subarrays with <code>k = 2</code> distinct integers, each appearing at least <code>m = 2</code> times are:</p>

<table style="border: 1px solid black;">
	<thead>
		<tr>
			<th style="border: 1px solid black;">Subarray</th>
			<th style="border: 1px solid black;">Distinct<br />
			numbers</th>
			<th style="border: 1px solid black;">Frequency</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td style="border: 1px solid black;">[1, 2, 1, 2]</td>
			<td style="border: 1px solid black;">{1, 2} &rarr; 2</td>
			<td style="border: 1px solid black;">{1: 2, 2: 2}</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;">[1, 2, 1, 2, 2]</td>
			<td style="border: 1px solid black;">{1, 2} &rarr; 2</td>
			<td style="border: 1px solid black;">{1: 2, 2: 3}</td>
		</tr>
	</tbody>
</table>

<p>Thus, the answer is 2.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,1,2,4], k = 2, m = 1</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>The possible subarrays with <code>k = 2</code> distinct integers, each appearing at least <code>m = 1</code> times are:</p>

<table style="border: 1px solid black;">
	<thead>
		<tr>
			<th style="border: 1px solid black;">Subarray</th>
			<th style="border: 1px solid black;">Distinct<br />
			numbers</th>
			<th style="border: 1px solid black;">Frequency</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td style="border: 1px solid black;">[3, 1]</td>
			<td style="border: 1px solid black;">{3, 1} &rarr; 2</td>
			<td style="border: 1px solid black;">{3: 1, 1: 1}</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;">[1, 2]</td>
			<td style="border: 1px solid black;">{1, 2} &rarr; 2</td>
			<td style="border: 1px solid black;">{1: 1, 2: 1}</td>
		</tr>
		<tr>
			<td style="border: 1px solid black;">[2, 4]</td>
			<td style="border: 1px solid black;">{2, 4} &rarr; 2</td>
			<td style="border: 1px solid black;">{2: 1, 4: 1}</td>
		</tr>
	</tbody>
</table>

<p>Thus, the answer is 3.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k, m &lt;= nums.length</code></li>
</ul>


Subarray	Distinct numbers	Frequency
[1, 2, 1, 2]	{1, 2} → 2	{1: 2, 2: 2}
[1, 2, 1, 2, 2]	{1, 2} → 2	{1: 2, 2: 3}

Subarray	Distinct numbers	Frequency
[3, 1]	{3, 1} → 2	{3: 1, 1: 1}
[1, 2]	{1, 2} → 2	{1: 1, 2: 1}
[2, 4]	{2, 4} → 2	{2: 1, 4: 1}