leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

number-of-good-pairs.dart (1092B)

      1 //Given a list of numbers return the number of good pairs
      2 //that can be returned. A good pair is there n[i] == n[j] and
      3 //i < j. 
      4 
      5 //To solve this I created a hashmap with all of the values and
      6 //the index they occured at. Then from there I iterated through
      7 //the map and added the total number of pairs that could be created 
      8 //from each number.
      9 
     10 //The time complexity of this is O(n).
     11 
     12 //Time: 219ms Beats: 100%
     13 //Memory: 144.2MB Beats: 8.57%
     14 
     15 class Solution {
     16   int numIdenticalPairs(List<int> nums) {
     17       Map<int,List<int>> vals = {};
     18       int count = 0;
     19       for(int i in nums){
     20           List<int> current = (vals[i] ?? []);
     21           current.add(count);
     22           vals[i] = current;
     23           count += 1;
     24       }
     25       int options = 0;
     26       for(var entry in vals.entries){
     27         List<int> curr_list = entry.value;
     28         options += sumAll(curr_list.length - 1); 
     29       }
     30       return options;
     31   }
     32   int sumAll(int original){
     33     if(original <= 1){
     34       return original;
     35     }
     36     int current = sumAll(original - 1);
     37     current = current + original;
     38     return current;
     39   }
     40 }