Longest Subarray With Restricted Pair Sums | Leetcode 4067 | Sliding Window | Hashmap

class Solution {
    unordered_map<int,int> mymap;

    bool isValid(vector<int>& nums,int r){
        for(auto [ele,freq]: mymap){

            // Case 1: ele + nums[r] = some existing element
            if(mymap.count(nums[r] + ele)){
                return false;
            }

            // Case 2: ele + another element = nums[r]
            int other = nums[r] - ele;

            if(other > 0 && mymap.count(other)){
                // If ele == other, we need 2 distinct occurrences
                if(ele != other || freq > 1)
                    return false;
            }
        }
        return true;
    }
public:
    int maxSubarray(vector<int>& nums) {
        int longest = 0;
        int n = nums.size();
        int l=0,r=0;

        while(r<n){
            if(isValid(nums,r)){ //Insert
                mymap[nums[r]]++;
                r++;
            }else{  //Remove
                mymap[nums[l]]--;
                if(mymap[nums[l]]==0)
                    mymap.erase(nums[l]);
                l++;
            }
            longest = max(longest,r-l);
        }
        return longest;
    }
};
/*
//JAVA
class Solution {
    HashMap<Integer, Integer> mymap = new HashMap<>();

    boolean isValid(int[] nums, int r) {
        for (Map.Entry<Integer, Integer> entry : mymap.entrySet()) {
            int ele = entry.getKey();
            int freq = entry.getValue();

            // Case 1: ele + nums[r] = some existing element
            if (mymap.containsKey(nums[r] + ele)) {
                return false;
            }

            // Case 2: ele + another element = nums[r]
            int other = nums[r] - ele;

            if (other > 0 && mymap.containsKey(other)) {
                // If ele == other, we need 2 distinct occurrences
                if (ele != other || freq > 1) {
                    return false;
                }
            }
        }

        return true;
    }

    public int maxSubarray(int[] nums) {
        int longest = 0;
        int n = nums.length;
        int l = 0, r = 0;

        while (r < n) {
            if (isValid(nums, r)) { // Insert
                mymap.put(nums[r], mymap.getOrDefault(nums[r], 0) + 1);
                r++;
            } else { // Remove
                mymap.put(nums[l], mymap.get(nums[l]) - 1);

                if (mymap.get(nums[l]) == 0) {
                    mymap.remove(nums[l]);
                }

                l++;
            }

            longest = Math.max(longest, r - l);
        }

        return longest;
    }
}

#Python
class Solution:
    def __init__(self):
        self.mymap = {}

    def isValid(self, nums, r):
        for ele, freq in self.mymap.items():

            # Case 1: ele + nums[r] = some existing element
            if nums[r] + ele in self.mymap:
                return False

            # Case 2: ele + another element = nums[r]
            other = nums[r] - ele

            if other > 0 and other in self.mymap:
                # If ele == other, we need 2 distinct occurrences
                if ele != other or freq > 1:
                    return False

        return True

    def maxSubarray(self, nums):
        longest = 0
        n = len(nums)
        l = 0
        r = 0

        while r < n:
            if self.isValid(nums, r):  # Insert
                self.mymap[nums[r]] = self.mymap.get(nums[r], 0) + 1
                r += 1

            else:  # Remove
                self.mymap[nums[l]] -= 1

                if self.mymap[nums[l]] == 0:
                    del self.mymap[nums[l]]

                l += 1

            longest = max(longest, r - l)

        return longest
*/