Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1865.html

1865. Finding Pairs With a Certain Sum

Level

Medium

Description

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

  1. Add a positive integer to an element of a given index in the array nums2.
  2. Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

  • FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
  • void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
  • int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]

Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // return 2; pairs (5,2), (5,4) make 3 + 5
findSumPairs.count(4);  // return 1; pair (5,0) makes 3 + 1
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i] <= 10^9
  • 1 <= nums2[i] <= 10^5
  • 0 <= index < nums2.length
  • 1 <= val <= 10^5
  • 1 <= tot <= 10^9
  • At most 1000 calls are made to add and count each.

Solution

In the class FindSumPairs, maintain the array nums2 and two maps map1 and map2 that store each number’s occurrences in nums1 and nums2 respectively.

For the constructor, initialize nums2 with the given nums2, and initialize the two maps with the given two arrays.

For add, obtain the original value and the new value of nums2[index], update map2 with the original value and the new value, and update nums2[index] with the new value.

For count, loop over map1, and for each entry, calculate the count from map2 that has sum equal to tot, and calculate the number of pairs. Finally, return the number of pairs.

  • class FindSumPairs {
    int[] nums2;
    Map<Integer, Integer> map1;
    Map<Integer, Integer> map2;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums2 = nums2;
        map1 = new HashMap<Integer, Integer>();
        map2 = new HashMap<Integer, Integer>();
        for (int num : nums1)
            map1.put(num, map1.getOrDefault(num, 0) + 1);
        for (int num : nums2)
            map2.put(num, map2.getOrDefault(num, 0) + 1);
    }
    
    public void add(int index, int val) {
        int prev = nums2[index], curr = nums2[index] + val;
        int count1 = map2.get(prev) - 1, count2 = map2.getOrDefault(curr, 0) + 1;
        if (count1 > 0)
            map2.put(prev, count1);
        else
            map2.remove(prev);
        map2.put(curr, count2);
        nums2[index] = curr;
    }
    
    public int count(int tot) {
        int totalCount = 0;
        for (Map.Entry<Integer, Integer> entry : map1.entrySet()) {
            int num = entry.getKey(), count1 = entry.getValue();
            int count2 = map2.getOrDefault(tot - num, 0);
            totalCount += count1 * count2;
        }
        return totalCount;
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs obj = new FindSumPairs(nums1, nums2);
 * obj.add(index,val);
 * int param_2 = obj.count(tot);
 */

############

class FindSumPairs {
    private int[] nums1;
    private int[] nums2;
    private Map<Integer, Integer> cnt = new HashMap<>();

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        for (int v : nums2) {
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);
        }
    }

    public void add(int index, int val) {
        int old = nums2[index];
        cnt.put(old, cnt.get(old) - 1);
        cnt.put(old + val, cnt.getOrDefault(old + val, 0) + 1);
        nums2[index] += val;
    }

    public int count(int tot) {
        int ans = 0;
        for (int v : nums1) {
            ans += cnt.getOrDefault(tot - v, 0);
        }
        return ans;
    }
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs obj = new FindSumPairs(nums1, nums2);
 * obj.add(index,val);
 * int param_2 = obj.count(tot);
 */

  • // OJ: https://leetcode.com/problems/finding-pairs-with-a-certain-sum/
// Time:
//      FindSumPairs: O(B)
//      add: O(1)
//      count: O(A)
// Space: O(A + B)
class FindSumPairs {
    vector<int> A, B;
    unordered_map<int, int> m;
public:
    FindSumPairs(vector<int>& A, vector<int>& B): A(A), B(B) {
        for (int n : B) m[n]++;
    }
    void add(int index, int val) {
        int n = B[index];
        if (--m[n] == 0) m.erase(n);
        B[index] += val;
        m[B[index]]++;
    }
    int count(int tot) {
        int ans = 0;
        for (int a : A) {
            if (m.count(tot - a)) ans += m[tot - a];
        }
        return ans;
    }
};

  • class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.cnt = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        old = self.nums2[index]
        self.cnt[old] -= 1
        self.cnt[old + val] += 1
        self.nums2[index] += val

    def count(self, tot: int) -> int:
        return sum(self.cnt[tot - v] for v in self.nums1)


# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

############

# 1865. Finding Pairs With a Certain Sum
# https://leetcode.com/problems/finding-pairs-with-a-certain-sum/

class FindSumPairs:

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums2 = nums2
        self.mp1 = collections.Counter(nums1)
        self.mp2 = collections.Counter(nums2)

    def add(self, index: int, val: int) -> None:
        num = self.nums2[index]
        self.mp2[num] -= 1
        self.nums2[index] += val
        self.mp2[num + val] += 1

    def count(self, tot: int) -> int:
        count = 0
        mp = collections.defaultdict(int)
        
        for k,v in self.mp1.items():
            if tot - k in self.mp2:
                count += v * self.mp2[tot - k]
        
        return count


# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)


  • type FindSumPairs struct {
	nums1 []int
	nums2 []int
	cnt   map[int]int
}

func Constructor(nums1 []int, nums2 []int) FindSumPairs {
	cnt := map[int]int{}
	for _, v := range nums2 {
		cnt[v]++
	}
	return FindSumPairs{nums1, nums2, cnt}
}

func (this *FindSumPairs) Add(index int, val int) {
	old := this.nums2[index]
	this.cnt[old]--
	this.cnt[old+val]++
	this.nums2[index] += val
}

func (this *FindSumPairs) Count(tot int) (ans int) {
	for _, v := range this.nums1 {
		ans += this.cnt[tot-v]
	}
	return
}

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * obj := Constructor(nums1, nums2);
 * obj.Add(index,val);
 * param_2 := obj.Count(tot);
 */

All Problems

All Solutions