❌

Normal view

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

POTD #19 – Count the number of possible triangles | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
8 January 2025 at 15:08

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/count-possible-triangles-1587115620/1

Given an integer array arr[]. Find the number of triangles that can be formed with three different array elements as lengths of three sides of the triangle.  A triangle with three given sides is only possible if sum of any two sides is always greater than the third side.


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]

My Approach


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

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 #13 – Subarrays with sum K | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
2 January 2025 at 17:11

Problem Statement

Geeks For Geeks: https://www.geeksforgeeks.org/problems/subarrays-with-sum-k/1

Given an unsorted array of integers, find the number of continuous subarrays having sum exactly equal to a given number k.


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.

My Approach 1 (Brute Force)

Initially i tried to solve it via bruteforce, but got timedout. 


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

My Approach 2 (Optimal)

After some time, searched for an approach, then came across prefix-sum . So tried to apply the same, 


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

Reference:

  1. https://takeuforward.org/arrays/count-subarray-sum-equals-k/
  2. https://www.youtube.com/watch?v=frf7qxiN2qU

POTD #11 – Longest Consecutive Subsequence | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
31 December 2024 at 17:43

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/longest-consecutive-subsequence2449/1

Given an array arr[] of non-negative integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.


Input: arr[] = [2, 6, 1, 9, 4, 5, 3]
Output: 6
Explanation: The consecutive numbers here are 1, 2, 3, 4, 5, 6. These 6 numbers form the longest consecutive subsquence.



Input: arr[] = [1, 9, 3, 10, 4, 20, 2]
Output: 4
Explanation: 1, 2, 3, 4 is the longest consecutive subsequence.

My Approach

1. Sort the array.Initialize two variables:

  • max_sequence to 1 (to store the length of the longest consecutive subsequence).
  • cont_sub_sequence to 1 (to track the current consecutive subsequence length).

2. Loop through the array starting from the second element:

  • If the current element is equal to the previous one, skip it (handle duplicates).
  • Else, if the difference between the current and previous element is 1:
    • Increment cont_sub_sequence by 1.
  • Otherwise:
    • Update max_sequence as the maximum of max_sequence and cont_sub_sequence.
    • Reset cont_sub_sequence to 1.

3. After the loop, update max_sequence one final time as the maximum of max_sequence and cont_sub_sequence.

4. Return max_sequence.


class Solution:
    
    # arr[] : the input array
    
    #Function to return length of longest subsequence of consecutive integers.
    def longestConsecutive(self,arr):
        #code here
        arr.sort()
        max_sequence = 1
        cont_sub_sequence = 1
        for itr in range(1, len(arr)):
            if arr[itr] == arr[itr-1]:
                continue
            elif arr[itr] - arr[itr-1] == 1:
                cont_sub_sequence += 1
            else:
                if cont_sub_sequence > max_sequence:
                    max_sequence = cont_sub_sequence
                cont_sub_sequence = 1
        
        if cont_sub_sequence > max_sequence:
            max_sequence = cont_sub_sequence
        return max_sequence

POTD #7 – Count pairs with given sum | Geeks For Geeks

✇Parotta Salna
By: Mr.ParottaSalna
26 December 2024 at 18:50

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/count-pairs-with-given-sum–150253/1

Given an array arr[] and an integer target. You have to find numbers of pairs in array arr[] which sums up to given target.


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

My Approach

Today’s problem is similar to Two Sum problem, but with a counter. 


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

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

❌
❌