Skip to content

Commit 9b066da

Browse files
cheehwatangcheehwatang
authored
Merge pull request #333 from cheehwatang/add-2006-CountNumberOfPairsWithAbsoluteDifferenceK
Add 2006. Count Number of Pairs With Absolute Difference K (Hash Table)
2 parents 667d669 + 8a7a614 commit 9b066da

File tree

2 files changed

+84
-16
lines changed

2 files changed

+84
-16
lines changed

‎README.md

Lines changed: 38 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 12th</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_HashTable.java">Hash Table</a>
36+
</td>
37+
<td align="center">
38+
<a href="#array">Array</a>,
39+
<a href="#hash-table">Hash Table</a>
40+
</td>
41+
</tr>
3042
<tr>
3143
<td align="center">September 11th</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>
@@ -74,17 +86,6 @@
7486
<a href="#dynamic-programming">Dynamic Programming</a>
7587
</td>
7688
</tr>
77-
<tr>
78-
<td align="center">September 7th</td>
79-
<td>1155. <a href="https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/">Number of Dice Rolls With Target Sum</a></td>
80-
<td align="center">$\text{\color{Dandelion}Medium}$</td>
81-
<td align="center">
82-
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/1155.%20Number%20of%20Dice%20Rolls%20With%20Target%20Sum/NumberOfDiceRollsWithTargetSum_Tabulation.java">Dynamic Programming - Tabulation</a>
83-
</td>
84-
<td align="center">
85-
<a href="#dynamic-programming">Dynamic Programming</a>
86-
</td>
87-
</tr>
8889
</table>
8990
</br>
9091
<hr>
@@ -1565,13 +1566,15 @@
15651566
<td align="center">2006</td>
15661567
<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>
15671568
<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>
1569+
<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>,
1570+
<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> or
1571+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_HashTable.java">Hash Table</a>
15701572
</td>
15711573
<td align="center">$\text{\color{TealBlue}Easy}$</td>
15721574
<td align="center">
15731575
<a href="#array">Array</a>,
1574-
<a href="#counting">Counting</a>
1576+
<a href="#counting">Counting</a>,
1577+
<a href="#hash-table">Hash Table</a>
15751578
</td>
15761579
<td></td>
15771580
</tr>
@@ -3383,10 +3386,12 @@
33833386
<td align="center">$\text{\color{TealBlue}Easy}$</td>
33843387
<td align="center">
33853388
<a href="#array">Array</a>,
3386-
<a href="#counting">Counting</a>
3389+
<a href="#counting">Counting</a>,
3390+
<a href="#hash-table">Hash Table</a>
33873391
</td>
33883392
<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>
3393+
<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> or
3394+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_HashTable.java"><em>Hash Table</em></a>
33903395
</td>
33913396
</tr>
33923397
<tr>
@@ -5554,6 +5559,23 @@
55545559
</td>
55555560
<td></td>
55565561
</tr>
5562+
<tr>
5563+
<td align="center">2006</td>
5564+
<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>
5565+
<td align="center">
5566+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_HashTable.java">Java</a>
5567+
</td>
5568+
<td align="center">$\text{\color{TealBlue}Easy}$</td>
5569+
<td align="center">
5570+
<a href="#array">Array</a>,
5571+
<a href="#counting">Counting</a>,
5572+
<a href="#hash-table">Hash Table</a>
5573+
</td>
5574+
<td>Solution Using
5575+
<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</em></a>,
5576+
<a href="https://github.com/cheehwatang/leetcode-java/blob/main/solutions/2006.%20Count%20Number%20of%20Pairs%20With%20Absolute%20Difference%20K/CountNumberOfPairsWithAbsoluteDifferenceK_Counting.java"><em>Counting</em></a>
5577+
</td>
5578+
</tr>
55575579
<tr>
55585580
<td align="center">2007</td>
55595581
<td><a href="https://leetcode.com/problems/find-original-array-from-doubled-array/">Find Original Array From Doubled Array</a></td>

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

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.cheehwatang.leetcode;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
// Time Complexity : O(n),
7+
// where 'n' is the length of 'nums'.
8+
// We traverse 'nums' to count the numbers in 'nums', and we traverse the HashMap with a maximum size of 'n'.
9+
//
10+
// Space Complexity : O(n),
11+
// where 'n' is the length of 'nums'.
12+
// The HashMap has a maximum size of 'n' if the numbers in 'nums' are all unique.
13+
14+
public class CountNumberOfPairsWithAbsoluteDifferenceK_HashTable {
15+
16+
// Approach:
17+
// Using a HashMap to record the frequency of occurrence for all the numbers in 'nums'.
18+
// This only add the number to the HashMap if it is in 'nums'.
19+
20+
public int countKDifference(int[] nums, int k) {
21+
22+
// Record the frequency for all the numbers into the HashMap.
23+
Map<Integer, Integer> map = new HashMap<>();
24+
for (int number : nums) {
25+
map.put(number, map.getOrDefault(number, 0) + 1);
26+
}
27+
28+
// The number of combinations is the multiples of both frequency.
29+
// e.g. [1,1,2,2,2] can have 2 * 3 = 6 combinations for k = 1.
30+
// Check for the frequency for both key - k and key + k, as the k difference can be in both directions.
31+
// Once the count is added, set the value of the number in the HashMap to 0, so that it will not be double counted.
32+
// Do note that we cannot remove the key-value pair,
33+
// as it causes Exceptions in the map.keySet() which uses an iterator.
34+
int count = 0;
35+
for (Integer key : map.keySet()) {
36+
if (map.containsKey(key - k)) {
37+
count += map.get(key) * map.get(key - k);
38+
}
39+
if (map.containsKey(key + k)) {
40+
count += map.get(key) * map.get(key + k);
41+
}
42+
map.put(key, 0);
43+
}
44+
return count;
45+
}
46+
}

0 commit comments

Comments
 (0)