Input: s = "geeksforgeeks"
Output: 7
Explanation: "eksforg" is the longest substring with all distinct characters.

Input: s = "abcdefabcbb"
Output: 6
Explanation: The longest substring with all distinct characters is "abcdef", which has a length of 6.

class Solution:
    def longestUniqueSubstr(self, s):
        # code here
        char_index = {}
        max_length = 0
        start = 0
        
        for i, char in enumerate(s):
            if char in char_index and char_index[char] >= start:
                start = char_index[char] + 1 #crux
            
            char_index[char] = i
            
            max_length = max(max_length, i - start + 1)
        
        return max_length
                

Input: arr[] = [4, 6, 3, 7]
Output: 3
Explanation: There are three triangles possible [3, 4, 6], [4, 6, 7] and [3, 6, 7]. Note that [3, 4, 7] is not a possible triangle.  

Input: arr[] = [10, 21, 22, 100, 101, 200, 300]
Output: 6
Explanation: There can be 6 possible triangles: [10, 21, 22], [21, 100, 101], [22, 100, 101], [10, 100, 101], [100, 101, 200] and [101, 200, 300]

class Solution:
    #Function to count the number of possible triangles.
    def countTriangles(self, arr):
        # code here
        arr.sort()
        n = len(arr)
        cnt = 0
        for itr in range(2, n):
            left = 0
            right = itr - 1
            
            while left < right:
                
                if arr[left] + arr[right] > arr[itr]:
                    cnt += right - left
                    right -= 1
                else:
                    left += 1
        return cnt

Input: arr[] = [7, 2, 5, 3], target = 8
Output: 2
Explanation: There are 2 pairs with sum less than 8: (2, 5) and (2, 3). 

Input: arr[] = [5, 2, 3, 2, 4, 1], target = 5
Output: 4
Explanation: There are 4 pairs whose sum is less than 5: (2, 2), (2, 1), (3, 1) and (2, 1).

class Solution:
    #Complete the below function
    def countPairs(self, arr, target):
        #Your code here
        arr.sort()
        n = len(arr)
        cnt = 0
        left = 0
        right = n - 1
        while right > left:
            if arr[right] + arr[left] < target:
                cnt += right - left
                left += 1
            elif arr[right] + arr[left] >= target:
                right -= 1
            
        return cnt
                    

Input: arr[] = [-3, -1, -1, 0, 1, 2], target = -2
Output: 4
Explanation: Two triplets that add up to -2 are:
arr[0] + arr[3] + arr[4] = (-3) + 0 + (1) = -2
arr[0] + arr[1] + arr[5] = (-3) + (-1) + (2) = -2
arr[0] + arr[2] + arr[5] = (-3) + (-1) + (2) = -2
arr[1] + arr[2] + arr[3] = (-1) + (-1) + (0) = -2

Input: arr[] = [-2, 0, 1, 1, 5], target = 1
Output: 0
Explanation: There is no triplet whose sum is equal to 1. 

class Solution:
    def countTriplets(self, arr, target):
        hash_set = {}
        total = len(arr)
        cnt = 0
        
        # Build the hash_set with indices for each value in arr
        for i in range(total):
            if arr[i] not in hash_set:
                hash_set[arr[i]] = []
            hash_set[arr[i]].append(i)
        
        # Iterate through all pairs (itr, jtr)
        for itr in range(total):
            for jtr in range(itr + 1, total):
                rem = target - arr[itr] - arr[jtr]
                
                # Check for remaining value in hash_set
                if rem in hash_set:
                    # Use binary search to count indices greater than jtr
                    indices = hash_set[rem]
                    low, high = 0, len(indices)
                    
                    while low < high:
                        mid = (low + high) // 2
                        if indices[mid] > jtr:
                            high = mid
                        else:
                            low = mid + 1
                    
                    cnt += len(indices) - low

        return cnt

class Solution:
    def countTriplets(self, arr, target):
        n = len(arr)
        res = 0
 
        for i in range(n - 2):
            left = i + 1
            right = n - 1

            while left < right:
                sum = arr[i] + arr[left] + arr[right]
    
                if sum < target:
                    left += 1
    
                elif sum > target:
                    right -= 1
    
                else:
                    ele1 = arr[left]
                    ele2 = arr[right]
                    cnt1 = 0
                    cnt2 = 0
    
                    while left <= right and arr[left] == ele1:
                        left += 1
                        cnt1 += 1
    
                    while left <= right and arr[right] == ele2:
                        right -= 1
                        cnt2 += 1

                    if ele1 == ele2:
                        res += (cnt1 * (cnt1 - 1)) // 2
                    else:
                        res += (cnt1 * cnt2)
    
        return res

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.

Input: arr = [9, 4, 20, 3, 10, 5], k = 33
Output: 2
Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.

Input: arr = [1, 3, 5], k = 0
Output: 0
Explaination: No subarray with 0 sum.

class Solution:
    def countSubarrays(self, arr, k):
        # code here
        continous_count = 0
        total_length = len(arr)
        for itr in range(total_length):
            _sum = arr[itr]
            # print("ITR", arr[itr])
            for jtr in range(itr+1, total_length):
                # print("JTR", arr[jtr])
                if _sum + arr[jtr] == k:
                    # print("SUM")
                    continous_count += 1
                _sum += arr[jtr]
        return continous_count

class Solution:
    def countSubarrays(self, arr, k):
        n = len(arr)
        pre_sum_map = {}
        pre_sum = 0
        cnt = 0
    
        pre_sum_map[0] = 1
        for i in range(n):
            pre_sum += arr[i]
            remove = pre_sum - k
            cnt += pre_sum_map.get(remove, 0)
            pre_sum_map[pre_sum] = pre_sum_map.get(pre_sum, 0) + 1
    
        return cnt

Input: arr[] = [1, 5, 7, -1, 5], target = 6 
Output: 3
Explanation: Pairs with sum 6 are (1, 5), (7, -1) and (1, 5). 

Input: arr[] = [1, 1, 1, 1], target = 2 
Output: 6
Explanation: Pairs with sum 2 are (1, 1), (1, 1), (1, 1), (1, 1), (1, 1).

Input: arr[] = [10, 12, 10, 15, -1], target = 125
Output: 0

class Solution:
    #Complete the below function
    def countPairs(self,arr, target):
        #Your code here
        hash_count = {}
        total_count = 0
        for num in arr:
            rem = target - num
            if hash_count.get(rem):
                total_count += hash_count.get(rem)
            hash_count[num] = hash_count.get(num, 0) + 1
        return total_count

Input: arr[] = [1, 4, 45, 6, 10, 8], target = 16
Output: true
Explanation: arr[3] + arr[4] = 6 + 10 = 16.

Input: arr[] = [1, 2, 4, 3, 6], target = 11
Output: false
Explanation: None of the pair makes a sum of 11.

#User function Template for python3
class Solution:
	def twoSum(self, arr, target):
		# code here
		maps = {}
		for item in arr:
		    rem = target - item
		    if maps.get(rem):
		        return True
		    maps[item] = True
		return False
		

Input: mat[][] = [[1, -1, 1],
                [-1, 0, 1],
                [1, -1, 1]]
Output: [[1, 0, 1],
        [0, 0, 0],
        [1, 0, 1]]
Explanation: mat[1][1] = 0, so all elements in row 1 and column 1 are updated to zeroes.

Input: mat[][] = [[0, 1, 2, 0],
                [3, 4, 5, 2],
                [1, 3, 1, 5]]
Output: [[0, 0, 0, 0],
        [0, 4, 5, 0],
        [0, 3, 1, 0]]
Explanation: mat[0][0] and mat[0][3] are 0s, so all elements in row 0, column 0 and column 3 are updated to zeroes.

#User function Template for python3
class Solution:
    
    
    def setMatrixZeroes(self, mat):
        rows_to_zeros = set()
        cols_to_zeros = set()
        
        rows = len(mat)
        cols = len(mat[0])
        
        for i in range(rows):
            for j in range(cols):
                if mat[i][j] == 0:
                    rows_to_zeros.add(i)
                    cols_to_zeros.add(j)
        
        for row in rows_to_zeros:
            for itr in range(cols):
                mat[row][itr] = 0
        
        
        for col in cols_to_zeros:
            for itr in range(rows):
                mat[itr][col] = 0       
        
        return mat

Input: mat[][] = [[3, 4, 9],[2, 5, 6],[9, 25, 27]], x = 9
Output: true
Explanation: 9 is present in the matrix, so the output is true.

Input: mat[][] = [[19, 22, 27, 38, 55, 67]], x = 56
Output: false
Explanation: 56 is not present in the matrix, so the output is false.

class Solution:
    def binary_search(self, arr, x, start, stop):
        if start > stop:
            return False
        mid = (start + stop) // 2
        if start == stop and arr[start] != x:
            return False
        if arr[mid] == x:
            result = self.binary_search(arr, x, 0, length)
        elif arr[mid] > x:
            return self.binary_search(arr, x, start, mid)
        else:
            return self.binary_search(arr, x, mid+1, stop)
    
    #Function to search a given number in row-column sorted matrix.
    def searchRowMatrix(self, mat, x): 
    	# code here 
    	length = len(mat[0]) - 1
    	for arr in mat:
            result = self.binary_search(arr, x, 0, length)
            if result:
                return True
        return False