Skip to content

Commit 667d669

Browse files
cheehwatangcheehwatang
authored
Merge pull request #332 from cheehwatang/add-2006-CountNumberOfPairsWithAbsoluteDifferenceK
Add 2006. Count Number of Pairs With Absolute Difference K (Counting)
2 parents f17a3a9 + ddfeb2a commit 667d669

File tree

2 files changed

+66
-16
lines changed

2 files changed

+66
-16
lines changed

‎README.md

Lines changed: 32 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,18 @@
2727
<th>Solution</th>
2828
<th>Topics</th>
2929
</tr>
30+
<tr>
31+
<td align="center">September 11th</td>
32+
<td>2006. <a href="https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/">Count Number of Pairs With Absolute Difference K</a></td>
33+
<td align="center">$\text{\color{TealBlue}Easy}$</td>
34+
<td align="center">
35+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_Counting.java">Counting</a>
36+
</td>
37+
<td align="center">
38+
<a href="#array">Array</a>,
39+
<a href="#counting">Counting</a>
40+
</td>
41+
</tr>
3042
<tr>
3143
<td align="center">September 10th</td>
3244
<td>2006. <a href="https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/">Count Number of Pairs With Absolute Difference K</a></td>
@@ -73,19 +85,6 @@
7385
<a href="#dynamic-programming">Dynamic Programming</a>
7486
</td>
7587
</tr>
76-
<tr>
77-
<td align="center">September 6th</td>
78-
<td>1137. <a href="https://leetcode.com/problems/n-th-tribonacci-number/">N-th Tribonacci Number</a></td>
79-
<td align="center">$\text{\color{TealBlue}Easy}$</td>
80-
<td align="center">
81-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/1137.%20N-th%20Tribonacci%20Number/NthTribonacciNumber_Recursive.java">Dynamic Programming - Memoization</a>
82-
</td>
83-
<td align="center">
84-
<a href="#dynamic-programming">Dynamic Programming</a>,
85-
<a href="#math">Math</a>,
86-
<a href="#memoization">Memoization</a>
87-
</td>
88-
</tr>
8988
</table>
9089
</br>
9190
<hr>
@@ -1565,12 +1564,14 @@
15651564
<tr>
15661565
<td align="center">2006</td>
15671566
<td><a href="https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/">Count Number of Pairs With Absolute Difference K</a></td>
1568-
<td align="center">
1569-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK.java">Java</a>
1567+
<td align="center">Java with
1568+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK.java">Brute Force</a> or
1569+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_Counting.java">Counting</a>
15701570
</td>
15711571
<td align="center">$\text{\color{TealBlue}Easy}$</td>
15721572
<td align="center">
1573-
<a href="#array">Array</a>
1573+
<a href="#array">Array</a>,
1574+
<a href="#counting">Counting</a>
15741575
</td>
15751576
<td></td>
15761577
</tr>
@@ -3373,6 +3374,21 @@
33733374
</td>
33743375
<td></td>
33753376
</tr>
3377+
<tr>
3378+
<td align="center">2006</td>
3379+
<td><a href="https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/">Count Number of Pairs With Absolute Difference K</a></td>
3380+
<td align="center">
3381+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_Counting.java">Java</a>
3382+
</td>
3383+
<td align="center">$\text{\color{TealBlue}Easy}$</td>
3384+
<td align="center">
3385+
<a href="#array">Array</a>,
3386+
<a href="#counting">Counting</a>
3387+
</td>
3388+
<td>Solution Using
3389+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK.java"><em>Brute Force Approach</em></a>
3390+
</td>
3391+
</tr>
33763392
<tr>
33773393
<td align="center">2131</td>
33783394
<td><a href="https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/">Longest Palindrome by Concatenating Two Letter Words</a></td>

‎solutions/2006. Count Number of Pairs With Absolute Difference K/CountNumberOfPairsWithAbsoluteDifferenceK_Counting.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package com.cheehwatang.leetcode;
2+
3+
// Time Complexity : O(n + k),
4+
// where 'n' is the length of 'nums', and 'k' is 'k'.
5+
// We traverse 'nums' to count the numbers in 'nums', and we traverse maximum 'k' length to get the count.
6+
//
7+
// Space Complexity : O(1),
8+
// as the auxiliary space used is independent of the input.
9+
10+
public class CountNumberOfPairsWithAbsoluteDifferenceK_Counting {
11+
12+
// Approach:
13+
// Using a counting array to record the frequency of occurrence for all the numbers in 'nums'.
14+
// Since we know the number ranges from 1 to 100, we can build array of that size to keep track.
15+
16+
public int countKDifference(int[] nums, int k) {
17+
18+
// Counting array of size 101, since it is 0-indexed.
19+
int[] countingArray = new int[100 + 1];
20+
21+
// Record the frequency for all the numbers.
22+
for (int number : nums) countingArray[number]++;
23+
24+
// The number of combinations is the multiples of both frequency.
25+
// e.g. [1,1,2,2,2] can have 2 * 3 = 6 combinations for k = 1.
26+
// Since we are traversing from 1 to 100, we will only add to the count if both i and i+k is > 0 frequency.
27+
// With that, we do not need to compare with i-k.
28+
int count = 0;
29+
for (int i = 1; i < countingArray.length - k; i++) {
30+
count += countingArray[i] * countingArray[i + k];
31+
}
32+
return count;
33+
}
34+
}

0 commit comments

Comments
 (0)