Number of Good Pairs

🏠 ⬅️ ➡️

Given an array of integers nums, return the number of good pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Example 1:

Input: nums = [1,2,3,1,1,3] Output: 4 Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1] Output: 6 Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3] Output: 0

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 6
    integer, dimension(n) :: nums
    integer :: i, j
    integer :: good_pairs

    ! Example 1
    nums = [1, 2, 3, 1, 1, 3]
    write (*, '(a, i0)') 'Example 1: ', good_pairs(nums)

    ! Example 2
    nums = [1, 1, 1, 1]
    write (*, '(a, i0)') 'Example 2: ', good_pairs(nums)

    ! Example 3
    nums = [1, 2, 3]
    write (*, '(a, i0)') 'Example 3: ', good_pairs(nums)

contains

    function good_pairs(nums) result(count)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer :: count
        integer :: i, j

        count = 0
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) == nums(j)) then
                    count = count + 1
                end if
            end do
        end do
    end function good_pairs

end program main
❌ Compiled
❌ Executed
❌ Correct 
module good_pairs

implicit none

contains

integer function good_pairs(nums) result(count)

integer, intent(in) :: nums(:)

integer :: i, j

count = 0

do i = 1, size(nums) - 1
do j = i + 1, size(nums)
if (nums(i) == nums(j) .and. i < j) then
count = count + 1
end if
end do
end do

end function good_pairs

end module good_pairs

program test_good_pairs

use good_pairs, only : good_pairs

implicit none

integer, parameter :: nums1(5) = [1, 2, 3, 1, 1, 3]
integer, parameter :: nums2(4) = [1, 1, 1, 1]
integer, parameter :: nums3(3) = [1, 2, 3]

write (*, '(a, i0)') 'Example 1:', good_pairs(nums1)
write (*, '(a, i0)') 'Example 2:', good_pairs(nums2)
write (*, '(a, i0)') 'Example 3:', good_pairs(nums3)

end program test_good_pairs
🌐 Data from online sources 
class UndergroundSystem:
    def __init__(self):
        self.check_in_data = {}
        self.travel_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in_data[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start_station, start_time = self.check_in_data[id]
        route = (start_station, stationName)
        if route not in self.travel_data:
            self.travel_data[route] = [0, 0]
        self.travel_data[route][0] += t - start_time
        self.travel_data[route][1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        route = (startStation, endStation)
        total_time, num_trips = self.travel_data[route]
        return total_time / num_trips

The algorithm uses two nested hashmaps (in Python, two nested dictionaries) to keep track of check-in/check-out data and travel-time data:

  1. The check_in_data hashmap stores the traveler's check-in station and time, with their ID as the key.
  2. When a user checks out, the starting station and check-in time are retrieved from check_in_data and combined with the check-out station and time to create a route key. The route key is then used to store the total travel time and the number of trips taken for that route in the travel_data hashmap.
  3. To retrieve the average time between two stations, the algorithm looks up the total time and trip count for the requested route and divides the total time by the trip count.

The algorithm has an O(1) average complexity for all operations (check-in, check-out, and getAverageTime) as it relies on hashing lookups and updates.

🌐 Data from online sources 
#include <unordered_map>
#include <string>

class UndergroundSystem {
public:
    unordered_map<int, pair<string, int>> check_in_data;
    unordered_map<string, pair<int, int>> travel_data;

    UndergroundSystem() {}

    void checkIn(int id, string stationName, int t) {
        check_in_data[id] = {stationName, t};
    }

    void checkOut(int id, string stationName, int t) {
        string startStation = check_in_data[id].first;
        int startTime = check_in_data[id].second;
        string route = startStation + "_" + stationName;
        travel_data[route].first += (t - startTime);
        travel_data[route].second += 1;
    }

    double getAverageTime(string startStation, string endStation) {
        string route = startStation + "_" + endStation;
        return (double)travel_data[route].first / travel_data[route].second;
    }
};

The algorithm uses two nested hashmaps (in Python, two nested dictionaries) to keep track of check-in/check-out data and travel-time data:

  1. The check_in_data hashmap stores the traveler's check-in station and time, with their ID as the key.
  2. When a user checks out, the starting station and check-in time are retrieved from check_in_data and combined with the check-out station and time to create a route key. The route key is then used to store the total travel time and the number of trips taken for that route in the travel_data hashmap.
  3. To retrieve the average time between two stations, the algorithm looks up the total time and trip count for the requested route and divides the total time by the trip count.

The algorithm has an O(1) average complexity for all operations (check-in, check-out, and getAverageTime) as it relies on hashing lookups and updates.