❌

Normal view

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

POTD #6 – Two Sum – Pair with Given Sum | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
26 December 2024 at 06:05

Problem Statement

Geeks For Geeks : https://www.geeksforgeeks.org/problems/key-pair5616/1

Given an array arr[] of positive integers and another integer target. Determine if there exists two distinct indices such that the sum of there elements is equals to target.

Examples


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.

My Approach

  • Iterate through the array
  • For each element, check whether the remaining (target – element) is also present in the array using the supportive hashmap.
  • If the remaining is also present then return True.
  • Else, save the element in the hashmap and go to the next element. 

#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

POTD #4 – Search in a sorted Matrix | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
24 December 2024 at 06:29

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/search-in-a-matrix-1587115621/1

Given a strictly sorted 2D matrix mat[][] of size n x m anda number x. Find whether the number x is present in the matrix or not.


Note: In a strictly sorted matrix, each row is sorted in strictly increasing order, and the first element of the ith row (i!=0) is greater than the last element of the (i-1)th row.


Input: mat[][] = [[1, 5, 9], [14, 20, 21], [30, 34, 43]], x = 14
Output: true
Explanation: 14 is present in the matrix, so output is true.

My Approach

Today’s problem is same as yesterday’s problem. 


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)
    
    #Function to search a given number in row-column sorted matrix.
    def searchMatrix(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

❌
❌