Last active
October 14, 2019 03:28
-
-
Save kirkdrichardson/e9171815b4c5bee6193a7b6959c0d6d1 to your computer and use it in GitHub Desktop.
Multiple Pointer Pattern (slinky variation) - algorithm challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * | |
| * Two Pointers Technique: | |
| * - Simple to implement | |
| * - Typically improves time complexity from O(n^2) to O(n). | |
| * - Often used for searching for pairs in a sorted array | |
| * | |
| * Write a fx named uniqueValues that accepts a sorted array, and | |
| * returns an integer representing the number of unique values in the array. | |
| * The array may contain negative values. | |
| * | |
| * See live @ https://dartpad.dartlang.org/e9171815b4c5bee6193a7b6959c0d6d1 | |
| * | |
| * uniqueValues([4, 4, 4, 4, 4]); // 1 | |
| * uniqueValues([2, 3, 4, 4]); // 3 | |
| * uniqueValues([-1, 0, 1, 2, 3, 4]); // 6 | |
| * uniqueValues([]); // 0 | |
| * uniqueValues([4, 4, 4, 5, 5, 5, 6, 6, 6]); // 3 | |
| * uniqueValues([99, 99, 88, 77, 0, -44, -44, -33, -33]); // 6 | |
| * | |
| * */ | |
| void main() { | |
| int result; | |
| result = uniqueValues([4, 4, 4, 4, 4]); // 1 | |
| print(result == 1); | |
| result = uniqueValues([2, 3, 4, 4]); // 3 | |
| print(result == 3); | |
| result = uniqueValues([-1, 0, 1, 2, 3, 4]); // 6 | |
| print(result == 6); | |
| result = uniqueValues([]); // 0 | |
| print(result == 0); | |
| result = uniqueValues([4, 4, 4, 5, 5, 5, 6, 6, 6]); // 3 | |
| print(result == 3); | |
| result = uniqueValues([99, 99, 88, 77, 0, -44, -44, -33, -33]); // 6 | |
| print(result == 6); | |
| } | |
| int uniqueValues(List<int> list) { | |
| // Early return for empty list. | |
| if (list.length == 0) return 0; | |
| // In this case, we have at least one unique value. | |
| int uniqueCount = 1; | |
| // Initialize our pointers at their starting indices | |
| int p1 = 0; | |
| int p2 = p1 + 1; | |
| // [2, 3, 4, 4] | |
| // ^ ^ | |
| // uniqueCount: 1 | |
| // [ 4, 4, 4, 5, 5, 5, 6, 6, 6 ] | |
| // p1 | |
| // p2 | |
| while (p2 < list.length) { | |
| if (list[p1] == list[p2]) p2++; | |
| else { | |
| p1 = p2; | |
| uniqueCount++; | |
| } | |
| } | |
| return uniqueCount; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment