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
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
Given an array arr[] and an integer target. You have to find the number of pairs in the array whose sum is strictly less than the target.
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).
My Approach
Sorted the array and used two pointer approach to find the possible pairs.
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
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[] = [-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
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.
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.
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
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.
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 ,
Iterate each array of the matrix.
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
Login
