❌

Normal view

There are new articles available, click to refresh the page.
Before yesterdayMain stream

POTD #22 – Longest substring with distinct characters | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
11 January 2025 at 16:44

Problem Statement

Geeks For Geeks : https://www.geeksforgeeks.org/problems/longest-distinct-characters-in-string5848/1

Given a string s, find the length of the longest substring with all distinct characters. 


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.

My Approach – Sliding Window


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

POTD #15 – Count all triplets with given sum in sorted array | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
4 January 2025 at 18:14

Problem Statement

Geeks For Geeks : https://www.geeksforgeeks.org/problems/count-all-triplets-with-given-sum-in-sorted-array/1

Given a sorted array arr[] and a target value, the task is to count triplets (i, j, k) of valid indices, such that arr[i] + arr[j] + arr[k] = target and i < j < k.


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.

My Approach:

Initially i tried to approach the problem, similar to this. All testcases but 1 passed. Initial time complexity is O(n3). Failed 6 times. 



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

Then after reading blogs, switched to Two Pointer method



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

POTD #3 Search in a row-wise sorted matrix | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
23 December 2024 at 10:25

Problem Statement

GFG Link – https://www.geeksforgeeks.org/problems/search-in-a-row-wise-sorted-matrix/1

Given a row-wise sorted 2D matrix mat[][] of size n x m andan integer x, find whether element x is present in the matrix.
Note: In a row-wise sorted matrix, each row is sorted in itself, i.e. for any i, j within bounds, mat[i][j] <= mat[i][j+1].

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.

My Approach:

Today’s problem is same as yesterday’s problem. But i got timed out. So instead of calculating the len(arr) each time (which is same always ) i just stored it in a variable and passed. 

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

POTD #2 Search in a Row-Column sorted matrix | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
22 December 2024 at 05:50

Second day of POTD Geeks For Geeks. https://www.geeksforgeeks.org/problems/search-in-a-matrix17201720/1.

Given a 2D integer matrix mat[][] of size n x m, where every row and column is sorted in increasing order and a number x,the task is to find whether element x is present in the matrix.

Examples:


Input: mat[][] = [[3, 30, 38],[20, 52, 54],[35, 60, 69]], x = 62
Output: false
Explanation: 62 is not present in the matrix, so output is false.


Input: mat[][] = [[18, 21, 27],[38, 55, 67]], x = 55
Output: true
Explanation: 55 is present in the matrix.

My Approach

The question states that every row in the matrix is sorted in ascending order. So we can use the binary search to find the element inside each array.

So ,

  1. Iterate each array of the matrix.
  2. Find the element in array using binary search.

#User function Template for python3
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:
            return True
        elif arr[mid] > x:
            return self.binary_search(arr, x, start, mid)
        else:
            return self.binary_search(arr, x, mid+1, stop)
        
        
    
    def matSearch(self, mat, x):
        # Complete this function
        for arr in mat:
            result = self.binary_search(arr, x, 0, len(arr)-1)
            if result:
                return True
        return False

❌
❌