• We need a subarray say from i to j such that sum of all elements is divisible by k.

  • sum_j means prefix sum from 0 to j

  • sum_i means prefix sum from 0 to i

     => (sum_j - sum_i) % k = 0
     => sum_j % k - sum % k = 0
     => sum_j % k = sum_i % k    <Relation derived !!!>
    

• Thus for some prefix_sum(0,j) , we need to check if there exist some prefix_sum(0,i) such that both are equal.

  • If yes then return true.

  • Otherwise check for some other j

• Lets do a dry run on first example:

  • Given, nums : 23 2 4 6 7 , k = 6

  • Prefix_Sum at every iteration from 0->i :

      i = 0  , prefixSum = 23%6 = 5       | map[5] = 0 (new entry)
      i = 1 , prefixSum = (5+2)%6 = 1     | map[1] = 1 (new entry)
      i = 2 , prefixSum = (1+4)%6 = 5     | map[5] (already exist) !! -> Possible answer
    

  • Also, i - map[5] = 2 > 1 ... therefore at least 2 elements condition is also satisfied

Code:

bool checkSubarraySum(vector<int>& nums, int k) {
     
    int prefSum = 0;
    unordered_map<int, int> mp;
    for(int i=0; i<nums.size(); i++)
    {
        prefSum += nums[i];
        prefSum %= k;

        if(prefSum == 0 && i) return true;

        // cout << prefSum << " ";
        if(mp.find(prefSum) != mp.end())  // Found the required prefix sum 
        {
            if(i - mp[prefSum] > 1) return true; // check if atleast 2 elements are there or not
        }
        else mp[prefSum] = i;
    }

    return false;
}

LOGIC :- Initially take all the 1's in both of the matrices into two different vectors. Or vector of pairs for our convinience as we are going to store the coordinates both x and y.

Now,

The main logic here is to simply map ! each of the 1's from first matrix to every 1 that is present in the other matrix.

Just do the same for all the other 1's in matrix1. And we keep track of overlapping that we get in all of these cases. The one with maximum overlapping is our answer.

int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n=img1.size();
        vector<pair<int,int>>vp1,vp2;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(img1[i][j]==1){
                    vp1.push_back({i,j});
                }
                if(img2[i][j]==1){
                    vp2.push_back({i,j});
                }
            }
        }
        int ans=0;
        map<pair<int,int>,int>mp;
        for(auto it1:vp1){
            for(auto it2:vp2){
                int a=it1.first-it2.first;
                int b=it1.second-it2.second;
                mp[{a,b}]++;
                ans=max(ans,mp[{a,b}]);
            }
        }
        return ans;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string s : strs) {
            string t = s; 
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> anagrams;
        for (auto p : mp) { 
            anagrams.push_back(p.second);
        }
        return anagrams;
    }
};