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
You are given a 2D matrix mat[][] of size n×m. The task is to modify the matrix such that if mat[i][j] is 0, all the elements in the i-th row and j-th column are set to 0 and do it in constant space complexity.
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.
My Approach
Iterate through the matrix and check whether mat[i][j] is zero. If its zero then row i and col j need to made as zeros.
Collect them in a set
Finally iterate through the set and update the matrix.
#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
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
