Just a challenge for me to see how far I can keep up by doing one coding question per day!
Given a number N, print all numbers in the range from 1 to N having exactly 3 divisors.
https://www.geeksforgeeks.org/numbers-exactly-3-divisors/
Examples:
Input : N = 16
Output : 4 9
4 and 9 have exactly three divisors.
Input : N = 49
Output : 4 9 25 49
4, 9, 25 and 49 have exactly three divisors.
Expected Time Complexity : O(N1/2 * N1/4)
Expected Auxilliary Space : O(1)
Constraints : 1 <= N <= 109
Solution: here
Given two integers ‘a’ and ‘m’, find modular multiplicative inverse of ‘a’ under modulo ‘m’.
The modular multiplicative inverse is an integer ‘x’ such that: a x ≅ 1 (mod m).
The value of x should be in {0, 1, 2, … m-1}, i.e., in the range of integer modulo m.
https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
Examples:
Input: a = 3, m = 11
Output: 4
Since (43) mod 11 = 1, 4 is modulo inverse of 3(under 11).
One might think, 15 also as a valid output as "(153) mod 11"
is also 1, but 15 is not in ring {0, 1, 2, ... 10}, so not
valid.
Input: a = 10, m = 17
Output: 12
Since (10*12) mod 17 = 1, 12 is modulo inverse of 10(under 17).
Expected Time Complexity : O(m)
Expected Auxilliary Space : O(1)
Constraints:
1 <= a <= 104
1 <= m <= 104
Solution: here
Given an array of integers, find the first repeating element in it.
We need to find the element that occurs more than once and whose index of first occurrence is smallest.
https://www.geeksforgeeks.org/find-first-repeating-element-array-integers/
Examples:
Input: arr[] = {10, 5, 3, 4, 3, 5, 6}
Output: 5 [5 is the first element that repeats]
Input: arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10}
Output: 6 [6 is the first element that repeats]
Expected Time Complexity: O(NlogN)
Expected Auxilliary Space: O(N)
Constraints:
1 <= N <= 106
0 <= Ai<= 106
Solution: here
Given an array arr[] of size n where every element is in range from 0 to n-1.
Rearrange the given array so that arr[i] becomes arr[arr[i]].
This should be done with O(1) extra space.
https://www.geeksforgeeks.org/rearrange-given-array-place/
Examples:
Input:
N = 2
arr[] = {1,0}
Output: 0 1
Input:
N = 5
arr[] = {4,0,2,1,3}
Output: 3 4 2 0 1
arr[arr[0]] is 3 so arr[0] in output array is 3
arr[arr[1]] is 4 so arr[1] in output array is 4
arr[arr[2]] is 2 so arr[2] in output array is 2
arr[arr[3]] is 0 so arr[3] in output array is 0
arr[arr[4]] is 1 so arr[4] in output array is 1
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 107
0 <= Arr[i] < N
Solution: here
Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it is able to trap after raining.
https://www.geeksforgeeks.org/trapping-rain-water/
Examples:
Input: arr[] = {2, 0, 2}
Output: 2
We can trap 2 units of water in the middle gap.
Input: arr[] = {3, 0, 2, 0, 4}
Output: 7
We can trap "3 units" of water between 3 and 2,"1 unit" on top of bar 2 and "3 units" between 2 and 4.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
3 <= N <= 107
0 <= Ai <= 108
Solution: here
We are given two sorted arrays.
We need to merge these two arrays such that the initial numbers (after complete sorting)
are in the first array and the remaining numbers are in the second array.
Extra space allowed in O(1).
https://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/
Examples:
Input: ar1[] = {10};
ar2[] = {2, 3};
Output: ar1[] = {2}
ar2[] = {3, 10}
Input: ar1[] = {1, 5, 9, 10, 15, 20};
ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
ar2[] = {10, 13, 15, 20}
Expected Time Complexity: O((n+m) log(n+m))
Expected Auxilliary Space: O(1)
Constraints:
1 <= X, Y <= 5*104
0 <= arr1i, arr2i <= 109
Solution: here
An element in a sorted array can be found in O(log n) time via binary search.
But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand.
So for instance, 1 2 3 4 5 might become 3 4 5 1 2.
Devise a way to find an element in the rotated array in O(log n) time.
https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/
Examples:
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
Output : Found at index 8
Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 30
Output : Not found
Input : arr[] = {30, 40, 50, 10, 20}
key = 10
Output : Found at index 3
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 107
0 ≤ Ai ≤ 108
1 ≤ K ≤ 108
Solution: here
Implement Merge Sort is a Divide and Conquer algorithm.
It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
The merge() function is used for merging two halves.
The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.
https://www.geeksforgeeks.org/merge-sort/
Expected Auxiliary Space: O(n)
Expected Time Complexity: O(n) for the merge() function only.
Constraints:
1 <= N <= 105
1 <= arr[i] <= 103
Solution: here
Given two sorted arrays, find their union.
https://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/
Examples:
Input : arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Output : Union : {1, 2, 3, 4, 5, 6, 7}
Input : arr1[] = {2, 5, 6}
arr2[] = {4, 6, 8, 10}
Output : Union : {2, 4, 5, 6, 8, 10}
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N+M)
Constraints:
1 <= N, M <= 105
1 <= arr[i], brr[i] <= 106
Solution: here
Given two sorted arrays, find their union.
https://www.geeksforgeeks.org/union-and-intersection-of-two-sorted-arrays-2/
Examples:
Input : arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Output : Intersection : {3, 5}
Input : arr1[] = {2, 5, 6}
arr2[] = {4, 6, 8, 10}
Output : Intersection : {6}
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N+M)
Constraints:
1 <= N, M <= 105
1 <= arr[i], brr[i] <= 106
Solution: here
Given an array of n distinct elements, find the minimum number of swaps required to sort the array.
https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/
Examples:
Input : {4, 3, 2, 1}
Output : 2
Explanation : Swap index 0 with 3 and 1 with 2 to form the sorted array {1, 2, 3, 4}.
Input : {1, 5, 4, 3, 2}
Output : 2
Expected Time Complexity: O(nlogn)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 105
1 ≤ numsi ≤ 106
Solution: [here]
Given an array “a[]” and integer “b”. Find whether b is present in a[] or not.
If present, then double the value of b and search again.
We repeat these steps until b is not found. Finally we return value of b.
https://www.geeksforgeeks.org/repeatedly-search-element-doubling-every-successful-search/
Examples:
Input : a[] = {1, 2, 3}
b = 1
Output :4
Initially we start with b = 1. Since it is present in array, it becomes 2.
Now 2 is also present in array b becomes 4 .Since 4 is not present, we return 4.
Input : a[] = {1 3 5 2 12}
b = 3
Output :6
Solution: here
Given arrival and departure times of all trains that reach a railway station,
the task is to find the minimum number of platforms required for the railway station so that no train waits.
We are given two arrays which represent arrival and departure times of trains that stop.
https://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
Examples:
Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
Explantion: There are at-most three trains at a time (time between 11:00 to 11:20)
Input: arr[] = {9:00, 9:40}
dep[] = {9:10, 12:00}
Output: 1
Explantion: Only one platform is needed.
Expected Time Complexity: O(nLogn)
Expected Auxiliary Space: O(n)
Constraints:
1 <= N <= 1000
1 <= A[i] < D[i] <= 2359
Solution: here
Given two sorted arrays, a[] and b[],
the task is to find the median of these sorted arrays,
in O(log n + log m) time complexity, when n is the number of elements in the first array,
and m is the number of elements in the second array.
https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/
Examples:
Input: ar1[] = {-5, 3, 6, 12, 15}
ar2[] = {-12, -10, -6, -3, 4, 10}
Output : The median is 3.
Explanation : The merged array is :
ar3[] = {-12, -10, -6, -5 , -3,
3, 4, 6, 10, 12, 15},
So the median of the merged array is 3
Input: ar1[] = {2, 3, 5, 8}
ar2[] = {10, 12, 14, 16, 18, 20}
Output : The median is 11.
Explanation : The merged array is :
ar3[] = {2, 3, 5, 8, 10, 12, 14, 16, 18, 20}
if the number of the elements are even,
so there are two middle elements,
take the average between the two :
(10 + 12) / 2 = 11.
Expected Time Complexity : O(log(max(m,n)))
Expected Auxilliary Space : O(n)
Constraints:
1 <= N, M <= 10^6
1 <= arr[i], brr[i] <= 10^7
Solution: here
Given an array A[] consisting 0s, 1s and 2s.
The task is to write a function that sorts the given array.
The functions should put all 0s first, then all 1s and all 2s in last.
https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/
Examples:
Input: {0, 1, 2, 0, 1, 2}
Output: {0, 0, 1, 1, 2, 2}
Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints: 1 <= N <= 10^5 0 <= A[i] <= 2
Solution: here
Demonstrate different matrix operations (Addition, Subtraction, Multiplication)
https://www.geeksforgeeks.org/different-operation-matrices/
Solution: here
Given an array of N elements, the task is to minimize the maximum difference of adjacent elements by inserting at most K elements in the array.
https://www.geeksforgeeks.org/minimize-the-maximum-difference-of-adjacent-elements-after-at-most-k-insertions/
Examples:
Input: arr = [2, 6, 8] K = 1
Output: 2
Explanation:
After insertion of 4 in between 2 and 6, the array becomes [2, 4, 6, 8]. In this case the maximum difference between any adjacent element is 2, which is the minimum that can be.
Input: arr = [3, 12] K = 2
Output: 3
Explanation:
After insertion of 6 and 9 in between 3 and 12, the array becomes [3, 6, 9, 12]. In this case the maximum difference between any adjacent element is 3, which is the minimum that can be.
Solution: here
Given a square matrix of size N x N. The task is to find the determinant of this matrix. https://www.geeksforgeeks.org/determinant-of-a-matrix/
Examples:
Input: N = 4
matrix[][] = {{1, 0, 2, -1},
{3, 0, 0, 5},
{2, 1, 4, -3},
{1, 0, 5, 0}}
Output: 30
Explanation:
Determinant of the given matrix is 30.
Input: N = 3
matrix[][] = {{1, 2, 3},
{4, 5, 6},
{7, 10, 9}}
Output: 12
Explanation:
Determinant of the given matrix is 12.
Expected Time Complexity: O(N^4)
Expected Auxiliary Space: O(N^2)
Constraints:
1 <= N <= 8
-10 <= mat[i][j] <= 10
Solution: here
Write a program to find the transpose of a square matrix of size N*N.
Transpose of a matrix is obtained by changing rows to columns and columns to rows.
https://www.geeksforgeeks.org/program-to-find-transpose-of-a-matrix/
Examples:
Input:
N = 4
mat[][] = {{1, 1, 1, 1},
{2, 2, 2, 2}
{3, 3, 3, 3}
{4, 4, 4, 4}}
Output:
{{1, 2, 3, 4},
{1, 2, 3, 4}
{1, 2, 3, 4}
{1, 2, 3, 4}}
Input:
N = 2
mat[][] = {{1, 2},
{-9, -2}}
Output:
{{1, -9},
{2, -2}}
Expected Time Complexity: O(N * N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 100
-10^3 <= mat[i][j] <= 10^3
Solution: here
Given a square matrix of size N x N.
The task is to rotate it by 90 degrees in anti-clockwise direction without using any extra space.
https://www.geeksforgeeks.org/rotate-a-matrix-by-90-degree-in-clockwise-direction-without-using-any-extra-space/
Examples:
Input:
N = 3
matrix[][] = {{1, 2, 3},
{4, 5, 6}
{7, 8, 9}}
Output:
Rotated Matrix:
3 6 9
2 5 8
1 4 7
Input:
N = 2
matrix[][] = {{1, 2},
{3, 4}}
Output:
Rotated Matrix:
2 4
1 3
Expected Time Complexity: O(N^2)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 100
1 <= matrix[][] <= 1000
Solution: here
Given a matrix of size R*C. Traverse the matrix in spiral form.
https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/
Examples:
Input:
R = 4, C = 4
matrix[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15,16}}
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Expected Time Complexity: O(RC)
Expected Auxiliary Space: O(RC)
Constraints:
1 <= R, C <= 100
0 <= matrixi <= 100
Solution: here
Given a matrix of size n x m, where every row and column is sorted in increasing order, and a number x.
Find whether element x is present in the matrix or not.
https://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/
Examples:
Input:
n = 3, m = 3, x = 62
matrix[][] = {{ 3, 30, 38},
{36, 43, 60},
{40, 51, 69}}
Output: 0
Explanation:
62 is not present in the matrix,
so output is 0.
Input:
n = 1, m = 6, x = 55
matrix[][] = {{18, 21, 27, 38, 55, 67}}
Output: 1
Explanation: 55 is present in the matrix.
Expected Time Complexity: O(N + M)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N, M <= 1000
1 <= mat[][] <= 10^5
1 <= X <= 1000
Solution: here
Given a binary matrix. Find the maximum area of a rectangle formed only of 1s in the given matrix.
https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/
Examples:
Input:
n = 4, m = 4
M[][] = {{0 1 1 0},
{1 1 1 1},
{1 1 1 1},
{1 1 0 0}}
Output: 8
Explanation: For the above test case the matrix will look like
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
the max size rectangle is
1 1 1 1
1 1 1 1
and area is 4 *2 = 8.
Expected Time Complexity : O(n*m)
Expected Auixiliary Space : O(m)
Constraints:
1<=n,m<=1000
0<=M[][]<=1
Solution: here
Given a number, find its corresponding Roman numeral.
https://www.geeksforgeeks.org/converting-decimal-number-lying-between-1-to-3999-to-roman-numerals/
Examples:
Input : 9
Output : IX
Input : 1904
Output : MCMIV
Expected Time Complexity: O(log10N)
Expected Auxiliary Space: O(log10N * 10)
Constraints:
1<=n<=3999
Solution: here
Given a string str. The task is to find the maximum occurring character in the string str.
If more than one character occurs the maximum number of time then print the lexicographically smaller character.
https://www.geeksforgeeks.org/maximum-occurring-character-in-an-input-string-set-2/
Examples:
Input:
str = testsample
Output: e
Explanation: e is the character which
is having the highest frequency.
Input:
str = output
Output: t
Explanation: t and u are the characters
with the same frequency, but t is
lexicographically smaller.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Number of distinct characters).
Note: N = |s|
Constraints: 1 ≤ |s| ≤ 100
Solution: here
You are given a string s. You need to find the missing characters in the string to make a panagram.
Note: The output characters will be lowercase and lexicographically sorted.
https://www.geeksforgeeks.org/missing-characters-make-string-pangram/
Examples:
Input:
s = Abcdefghijklmnopqrstuvwxy
Output: z
Input:
s = Abc
Output: defghijklmnopqrstuvwxyz
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 <= |s| <= 10000
Solution: here
The generalized form of an IPv4 address is (0-255).(0-255).(0-255).(0-255).
Here we are considering numbers only from 0 to 255 and any additional leading zeroes will be considered invalid.
https://www.geeksforgeeks.org/program-to-validate-an-ip-address/
Examples:
Input:
ip = 222.111.111.111
Output: 1
Input:
ip = 5555..555
Output: 0
Explanation: 5555..555 is not a valid
ip address, as the middle two portions
are missing.
Expected Time Complexity: O(N), N = length of string.
Expected Auxiliary Space: O(1)
Constraints:
1<=length of string <=50
Solution: here
Given two strings s1 and s2, find if s1 is a substring of s2.
If yes, return the index of the first occurrence, else return -1.
https://www.geeksforgeeks.org/check-string-substring-another/
Examples:
Input: s1 = "for", s2 = "geeksforgeeks"
Output: 5
Explanation:
String "for" is present as a substring
of s2.
Input: s1 = "practice", s2 = "geeksforgeeks"
Output: -1.
Explanation:
There is no occurrence of "practice" in
"geeksforgeeks"
Expected Time Complexity: O(|s|*|x|)
Expected Auxiliary Space: O(1)
Constraints:
1 <= |s|,|x| <= 1000
Solution: here
Given two strings 'str1' and 'str2', check if these two strings are isomorphic to each other. Two strings str1 and str2 are called isomorphic if there is a one to one mapping possible for every character of str1 to every character of str2 while preserving the order. https://www.geeksforgeeks.org/check-if-two-given-strings-are-isomorphic-to-each-other/
Examples:
Input: str1 = "aab", str2 = "xxy"
Output: True
'a' is mapped to 'x' and 'b' is mapped to 'y'.
Input: str1 = "aab", str2 = "xyz"
Output: False
One occurrence of 'a' in str1 has 'x' in str2 and
other occurrence of 'a' has 'y'.
Expected Time Complexity: O(|str1|+|str2|).
Expected Auxiliary Space: O(Number of different characters).
Note: |s| represents the length of string s.
Constraints:
1 <= |str1|, |str2| <= 10^3
Solution: here
Given two strings s1 and s2.
The task is to check if s2 is a rotated version of the string s1.
The characters in the strings are in lowercase.
https://www.geeksforgeeks.org/a-program-to-check-if-strings-are-rotations-of-each-other/
Examples:
Input:
geeksforgeeks
forgeeksgeeks
Output: 1
Explanation: s1 is geeksforgeeks, s2 is forgeeksgeeks. Clearly, s2 is a rotated
version of s1 as s2 can be obtained by left-rotating s1 by 5 units.
Input:
mightandmagic
andmagicmigth
Output: 0
Explanation: Here with any amount of rotation s2 can't be obtained by s1.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1 <= |s1|, |s2| <= 10^7
Solution: here
Given a string S, find the length of its longest substring that does not have any repeating characters.
https://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/
Examples:
Input:
S = geeksforgeeks
Output: 7
Explanation: The longest substring
without repeated characters is "ksforge".
Input:
S = abbcdb
Output: 3
Explanation: The longest substring is
"bcd". Here "abcd" is not a substring
of the given string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
0<= N <= 10^5
Solution: here
Given two numbers as stings s1 and s2. Calculate their Product.
https://www.geeksforgeeks.org/multiply-large-numbers-represented-as-strings/
Examples:
Input : num1 = 4154
num2 = 51454
Output : 213739916
Input : num1 = 654154154151454545415415454
num2 = 63516561563156316545145146514654
Output : 41549622603955309777243716069997997007620439937711509062916
Expected Time Complexity: O(n1* n2)
Expected Auxiliary Space: O(n1 + n2) ; where n1 and n2 are sizes of strings s1 and s2 respectively.
Constraints: 1 <= length of s1 and s2 <= 10^3
Solution: here
Given two strings a and b consisting of lowercase characters.
The task is to check whether two given strings are an anagram of each other or not.
An anagram of a string is another string that contains the same characters, only the order of characters can be different.
For example, “act” and “tac” are an anagram of each other.
https://www.geeksforgeeks.org/check-whether-two-strings-are-anagram-of-each-other/
Examples:
Input:
a = geeksforgeeks, b = forgeeksgeeks
Output: YES
Explanation: Both the string have same
characters with same frequency. So,
both are anagrams.
Input:
a = allergy, b = allergic
Output: NO
Explanation:Characters in both the strings
are not same, so they are not anagrams.
Expected Time Complexity: O(|a|+|b|).
Expected Auxiliary Space: O(Number of distinct characters).
Constraints: 1 ≤ |a|,|b| ≤ 10^5
Solution: here
Given a positive integer N, return its corresponding column title as it would appear in an Excel sheet.
For N =1 we have column A, for 27 we have AA and so on.
https://www.geeksforgeeks.org/find-excel-column-name-given-number/
Examples:
Input:
N = 51
Output: AY
Expected Time Complexity: O(Log(N))
Expected Auxiliary Space: O(Log(N))
Constraints: 1 ≤ N ≤ 10^7
Solution: here
Given a String S, reverse the string without reversing its individual words. Words are separated by dots.
https://www.geeksforgeeks.org/reverse-words-in-a-given-string/
Examples:
Input:
S = i.like.this.program.very.much
Output: much.very.program.this.like.i
Input:
S = pqr.mno
Output: mno.pqr
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints: 1 <= |S| <= 2000
Solution: here
Given a number N and a bit number K, check if Kth bit of N is set or not.
https://www.geeksforgeeks.org/check-whether-k-th-bit-set-not/
Examples:
Input: N = 4, K = 0
Output: No
Explanation: Binary representation of 4 is 100,
in which 0th bit from LSB is not set.
So, return false.
Input: N = 4, K = 2
Output: Yes
Explanation: Binary representation of 4 is 100,
in which 2nd bit from LSB is set.
So, return true.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^9
0 ≤ K ≤ floor(log2(N) + 1)
Solution: here
Given a positive integer N. The task is to check if N is a power of 2.
More formally, check if N can be expressed as 2x for some x.
https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/
Examples:
Input: N = 1
Output: true
Explanation: 1 is equal to 2 raised to 0 (20 == 1).
Input: N = 98
Output: false
Explanation:
98 cannot be obtained by any power of 2.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
0 <= N <= 10^18
Solution: here
Check if a given number is Sparse or not.
https://www.geeksforgeeks.org/check-if-a-given-number-is-sparse-or-not/
Examples:
Input: x = 72
Output: true
Explanation: Binary representation of 72 is 01001000.
There are no two consecutive 1's in binary representation
Input: x = 12
Output: false
Explanation: Binary representation of 12 is 1100.
Third and fourth bits (from end) are set.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints: 1 <= N <= 10^6
Solution: here
You are given two numbers A and B.
The task is to count the number of bits needed to be flipped to convert A to B.
https://www.geeksforgeeks.org/count-number-of-bits-to-be-flipped-to-convert-a-to-b/
Examples:
Input : a = 10, b = 20
Output : 4
Input : a = 7, b = 10
Output : 3
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints: 1 <= N <= 10^6
Solution: here
Show binary-to-gray and gray-to-binary conversions of a number.
Solution: here
Given an integer an N. The task is to return the position of first set bit found from the right side in the binary representation of the number.
Note: If there is no set bit in the integer N, then return 0 from the function.
https://www.geeksforgeeks.org/position-of-rightmost-set-bit/
Examples:
Input: N = 18
Output: 2
Explanation: Binary representation of
18 is 010010,the first set bit from the
right side is at position 2.
Input: N = 12
Output: 3
Explanation: Binary representation
of 12 is 1100, the first set bit
from the right side is at position 3.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints: 0 <= N <= 10^8
Solution: here
You are given a number N. Find the total count of set bits for all numbers from 1 to N(both inclusive)
https://www.geeksforgeeks.org/count-total-set-bits-in-all-numbers-from-1-to-n/
Examples:
Input: N = 4
Output: 5
Explanation:
For numbers from 1 to 4.
For 1: 0 0 1 = 1 set bits
For 2: 0 1 0 = 1 set bits
For 3: 0 1 1 = 2 set bits
For 4: 1 0 0 = 1 set bits
Therefore, the total set bits is 5.
Input: N = 17
Output: 35
Explanation: From numbers 1 to 17(both inclusive),
the total number of set bits is 35.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints: 1 ≤ N ≤ 10^8
Solution: here
Given two numbers M and N. The task is to find the position of the rightmost different bit in the binary representation of numbers.
https://www.geeksforgeeks.org/position-rightmost-different-bit/
Examples:
Input: m = 11, n = 9
Output: 2
(11)10 = (1011)2
(9)10 = (1001)2
It can be seen that 2nd bit from
the right is different
Input: m = 52, n = 4
Output: 5
(52)10 = (110100)2
(4)10 = (100)2
It can be seen that 5th bit from
the right is different
Expected Time Complexity: O(max(log m, log n))
Expected Auxiliary Space: O(1).
Constraints:
1 <= M <= 10^9
1 <= N <= 10^9
Solution: here
Given an set of positive integers. Find the maximum XOR subset value in the given set. Expected time complexity O(n).
https://www.geeksforgeeks.org/find-maximum-subset-xor-given-set/
Examples:
Input: set[] = {2, 4, 5}
Output: 7
The subset {2, 5} has maximum XOR value
Input: set[] = {9, 8, 5}
Output: 13
The subset {8, 5} has maximum XOR value
Expected Time Complexity : O(N*Log(max(arr[i])))
Expected Auxiliary Space : O(1)
Contraints :
1 <= N <= 10^5
1 <= arr[i] <= 10^6
Solution: here
Given an unsigned integer N. The task is to swap all odd bits with even bits.
https://www.geeksforgeeks.org/swap-all-odd-and-even-bits/
Examples:
Input: N = 23
Output: 43
Explanation:
Binary representation of the given number
is 00010111 after swapping
00101011 = 43 in decimal.
Input: N = 2
Output: 1
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints: 1 ≤ N ≤ 10^9
Solution: here
Given two arrays A and B of equal size N, the task is to find if given arrays are equal or not.
Two arrays are said to be equal if both of them contain same set of elements,
arrangements (or permutation) of elements may be different though.
Note : If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
https://www.geeksforgeeks.org/check-if-two-arrays-are-equal-or-not/
Examples:
Input:
N = 5
A[] = {1,2,5,4,0}
B[] = {2,4,5,0,1}
Output: 1
Explanation: Both the array can be
rearranged to {0,1,2,4,5}
Input:
N = 3
A[] = {1,2,5}
B[] = {2,4,15}
Output: 0
Explanation: A[] and B[] have only
one common value.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1<=N<=10^7
1<=A[],B[]<=10^18
Solution: here
Given an array with repeated elements, the task is to find the maximum distance two occurrences of an element.
https://www.geeksforgeeks.org/maximum-distance-two-occurrences-element-array/
Examples:
Input : arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Output: 10
Explanation:
maximum distance for 2 is 11-1 = 10
maximum distance for 1 is 4-2 = 2
maximum distance for 4 is 10-5 = 5
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(N)
Constraints: 1<=N<=10^6
Solution: here
Given an array of positive integers and an integer.
Determine whether or not there exist two elements in A whose sum is exactly equal to that integer.
https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/
Examples:
Input: arr[] = {0, -1, 2, -3, 1}
sum = -2
Output: -3, 1
If we calculate the sum of the output,
1 + (-3) = -2
Input: arr[] = {1, -2, 1, 0, 5}
sum = 0
Output: -1
No valid pair exists
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^5
1 ≤ X ≤ 2*10^5
Solution: here
Given an array of integers, sort the array according to frequency of elements. That is elements that have higher frequency come first.
If frequencies of two elements are same, then smaller number comes first.
https://www.geeksforgeeks.org/sort-elements-by-frequency/
Examples:
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^5
Solution: here
Find all the non-repeating element in a given array of integers.
Examples:
Input:
n = 10
arr[] = {1,1,2,2,3,3,4,5,6,7}
Output: 4 5 6 7
Input:
n = 5
arr[] = {10,20,40,30,10}
Output: 20 40 30
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n).
Constraints:
1 <= n <= 10^3
0 <= arr_i <= 10^7
Solution: here
You are given an array arr[] of size n. Find the total count of sub-arrays having their sum equal to 0.
https://www.geeksforgeeks.org/print-all-subarrays-with-0-sum/
Examples:
Input:
n = 6
arr[] = {0,0,5,5,0,0}
Output: 6
Explanation: The 6 subarrays are
[0], [0], [0], [0], [0,0], and [0,0].
Input:
n = 10
arr[] = {6,-1,-3,4,-2,2,4,6,-12,-7}
Output: 4
Explanation: The 4 subarrays are [-1 -3 4]
[-2 2], [2 4 6 -12], and [-1 -3 4 -2 2]
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(n)
Constraints:
1<= n <= 10^7
-10^10 <= arr_i <= 10^10
Solution: here
Given a non-empty array of integers, find the top k elements which have the highest frequency in the array.
If two numbers have the same frequency then the larger number should be given preference.
https://www.geeksforgeeks.org/find-k-numbers-occurrences-given-array/
Examples:
Input:
nums = {1,1,1,2,2,3}
k = 2
Output: {1, 2}
Input:
nums = {1,1,2,2,3,3,3,4}
k = 2
Output: {3, 2}
Explanation: Elements 1 and 2 have the same frequency ie. 2.
Therefore, in this case, the answer includes the element 2 as 2 > 1.
Expected Time Complexity : O(NlogN)
Expected Auxilliary Space : O(N)
Constraints:
1 <= N <= 10^3
1<=A[i]<=10^4
Solution: here
Given two integer arrays A1[ ] and A2[ ] of size N and M respectively.
Sort the first array A1[ ] such that all the relative positions of the elements in the first array are the same
as the elements in the second array A2[ ].
https://www.geeksforgeeks.org/sort-array-according-order-defined-another-array/
Examples:
Input: N = 11 M = 4
A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
A2[] = {2, 1, 8, 3}
Output: 2 2 1 1 8 8 3 5 6 7 9
Input: N = 11 M = 4
A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
A2[] = {99, 22, 444, 56}
Output: 1 1 2 2 3 5 6 7 8 8 9
Expected Time Complexity : O(NlogN)
Expected Auxilliary Space : O(N)
Constraints:
1 ≤ N, M ≤ 10^6
1 ≤ A1[i], A2[i] ≤ 10^6
Solution: here
Given an array having both positive and negative integers.
The task is to compute the length of the largest subarray with sum 0.
https://www.geeksforgeeks.org/find-the-largest-subarray-with-0-sum/
Examples:
Input:
N = 8
A[] = {15,-2,2,-8,1,7,10,23}
Output: 5
Explanation: The largest subarray with
sum 0 will be -2 2 -8 1 7.
Expected Time Complexity : O(NlogN)
Expected Auxilliary Space : O(N)
Constraints:
1 <= N <= 10^4
-1000 <= A[i] <= 1000, for each valid i
Solution: here
Given an array of integers, find anyone combination of four elements in the array whose sum is equal to a given value X.
https://www.geeksforgeeks.org/find-four-elements-that-sum-to-a-given-value-set-2/
Examples:
Input: array = {10, 2, 3, 4, 5, 9, 7, 8}
X = 23
Output: 3 5 7 8
Sum of output is equal to 23,
i.e. 3 + 5 + 7 + 8 = 23.
Input: array = {1, 2, 3, 4, 5, 9, 7, 8}
X = 16
Output: 1 3 5 7
Sum of output is equal to 16,
i.e. 1 + 3 + 5 + 7 = 16.
Expected Time Complexity: O(N^3).
Expected Auxiliary Space: O(N^2).
Constraints:
1 <= N <= 100
-1000 <= K <= 1000
-100 <= A[i] <= 100
Solution: here
Given an array of size n and an integer k, return the count of distinct numbers in all windows of size k.
https://www.geeksforgeeks.org/count-distinct-elements-in-every-window-of-size-k/
Examples:
Input: arr[] = {1, 2, 1, 3, 4, 2, 3};
k = 4
Output: 3 4 4 3
Explanation:
First window is {1, 2, 1, 3}, count of distinct numbers is 3
Second window is {2, 1, 3, 4} count of distinct numbers is 4
Third window is {1, 3, 4, 2} count of distinct numbers is 4
Fourth window is {3, 4, 2, 3} count of distinct numbers is 3
Expected Time Complexity: O(N*k).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= K <= 10^5
1 <= A[i] <= 10^5 , for each valid i
Solution: here
Given a linked list. Print all the elements of the linked list
Examples:
Input: N = 2
LinkedList= {1 , 2}
Output: 1 2
Expected Time Complexity : O(N)
Expected Auxiliary Space : O(1)
Constraints :
1 <= N <= 100
Solution: here
Given a linked list of N nodes. The task is to reverse this list.
https://www.geeksforgeeks.org/reverse-a-linked-list/
Examples:
Input:
LinkedList: 1->2->3->4->5->6
Output: 6 5 4 3 2 1
Explanation: After reversing the list, elements are 6->5->4->3->2->1
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^4
Solution: here
Given a singly linked list and a key, count the number of occurrences of given key in the linked list.
https://www.geeksforgeeks.org/write-a-function-that-counts-the-number-of-times-a-given-int-occurs-in-a-linked-list/
Examples:
Input:
N = 7
Link List = 1->2->1->2->1->3->1
search_for = 1
Output: 4
Explanation:1 appears 4 times.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 10^4
Solution: here
Given a singly linked list of size N. The task is to swap elements in the linked list pairwise.
https://www.geeksforgeeks.org/pairwise-swap-elements-of-a-given-linked-list-by-changing-links/
Examples:
Input:
LinkedList: 1->3->4->7->9->10->1
Output: 3 1 7 4 10 9 1
Explanation: After swapping each pair
considering (1,3), (4, 7), (9, 10).. so
on as pairs, we get 3, 1, 7, 4, 10, 9,
1 as a new linked list.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^3
Solution: here
Given two numbers represented by two linked lists of size N and M.
The task is to return a sum list.
The sum list is a linked list representation of the addition of two input numbers.
https://www.geeksforgeeks.org/sum-of-two-linked-lists/
Examples:
Input: N = 2
valueN[] = {4,5}
M = 3
valueM[] = {3,4,5}
Output: 3 9 0
Explanation: For the given two linked
list (4 5) and (3 4 5), after adding
the two linked list resultant linked
list will be (3 9 0)
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(Max(N,M))
Constraints: 1 <= N, M <= 5000
Solution: here
Write a function to insert a new value in a sorted Circular Linked List (CLL)
Given a sorted circular linked list, the task is to insert a new node in this circular list
so that it remains a sorted circular linked list.
https://www.geeksforgeeks.org/sorted-insert-for-circular-linked-list/
Examples:
Input:
LinkedList = 1->2->4
(the first and last node is connected,
i.e. 4 --> 1)
data = 2
Output: 1 2 2 4
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints: 0 <= N <= 10^5
Solution: here
Given a Cirular Linked List of size N, split it into two halves circular lists.
If there are odd number of nodes in the given circular linked list then out of the resulting two halved lists,
first list should have one node more than the second list.
The resultant lists should also be circular lists and not linear lists.
https://www.geeksforgeeks.org/split-a-circular-linked-list-into-two-halves/
Examples:
Input:
Circular LinkedList: 1->5->7
Output:
1 5
7
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
Constraints: 1 <= N <= 100
Solution: here
Given a linked list of size N. The task is to reverse every k nodes (where k is an input to the function) in the linked list.
https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
Examples:
Input:
LinkedList: 1->2->2->4->5->6->7->8
K = 4
Output: 4 2 2 1 8 7 6 5
Explanation:
The first 4 elements 1,2,2,4 are reversed first
and then the next 4 elements 5,6,7,8. Hence, the
resultant linked list is 4->2->2->1->8->7->6->5.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 10⁴
1 <= k <= N
Solution: here
Given a linked list of N nodes. The task is to check if the linked list has a loop. Linked list can contain self loop.
https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/
Examples:
Input:
N = 3
value[] = {1,3,4}
x = 2
Output: True
Explanation: In above test case N = 3.
The linked list with nodes N = 3 is
given. Then value of x=2 is given which
means last node is connected with xth
node of linked list. Therefore, there
exists a loop.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^4
1 <= Data on Node <= 10^3
Solution: here
Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other.
https://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/
Examples:
Input:
LinkList1 = 3->6->9->common
LinkList2 = 10->common
common = 15->30->NULL
Output: 15
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N + M ≤ 2*10^5
-1000 ≤ value ≤ 1000
Solution: here
Given a singly linked list, delete middle of the linked list.
For example, if given linked list is 1->2->3->4->5 then linked list should be modified to 1->2->4->5.
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element.
For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL or has 1 node, then it should return NULL
https://www.geeksforgeeks.org/delete-middle-of-linked-list/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 1000
1 <= value <= 1000
Solution: here
You are given a special linked list with N nodes where each node has a next pointer pointing to its next node.
You are also given M random pointers , where you will be given M number of pairs denoting two nodes a and b
i.e. a->arb = b.
https://www.geeksforgeeks.org/clone-linked-list-next-random-pointer-o1-space/
Examples:
Input:
N = 4, M = 2
value = {1,2,3,4}
pairs = {{1,2},{2,4}}
Output: 1
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 100
1 <= M <= N
1 <= a, b <= 100
Solution: here
Sort the given Linked List using quicksort. which takes O(n^2) time in worst case and O(nLogn) in average and best cases.
https://www.geeksforgeeks.org/quicksort-on-singly-linked-list/
Examples:
Input:
1 6 2
Output:
1 2 6
Constraints:
1<=T<=100
1<=N<=200
Solution: here
Given a Cirular Linked List of size N, split it into two halves circular lists.
If there are odd number of nodes in the given circular linked list then out of the resulting two halved lists,
first list should have one node more than the second list.
The resultant lists should also be circular lists and not linear lists.
https://www.geeksforgeeks.org/deletion-at-different-positions-in-a-circular-linked-list/
Examples:
LinkedList: 1->2->3->4->5
position: 4
Output: 1 2 3 5
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
2 <= number of nodes <= 10^3
1 <= pos <= n
Solution: here
Sort the given doubly linked list of size N using quicksort.
Just complete the partition function using the quicksort technique.
https://www.geeksforgeeks.org/quicksort-for-linked-list/
Examples:
Input:
LinkedList: 4->2->9
Output:2 4 9
Expected Time Complexity: O(NlogN)
Expected Auxilliary Space: O(1)
Constraints: 1 <= N <= 200
Solution: here
You are given a pointer/ reference to the node which is to be deleted from the linked list of N nodes.
The task is to delete the node. Pointer/ reference to head node is not given.
Note: No head reference is given to you.
It is guaranteed that the node to be deleted is not a tail node in the linked list.
https://www.geeksforgeeks.org/delete-a-node-from-linked-list-without-head-pointer/
Examples:
Input:
N = 2
value[] = {1,2}
node = 1
Output: 2
Explanation: After deleting 1 from the
linked list, we have remaining nodes
as 2.
Expected Time Complexity : O(1)
Expected Auxilliary Space : O(1)
Constraints: 1 <= N <= 103
Solution: here
Given Pointer/Reference to the head of a doubly linked list of N nodes,
the task is to Sort the given doubly linked list using Merge Sort in both non-decreasing and non-increasing order.
https://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/
Examples:
Input: N = 8
value[] = {7,3,5,2,6,4,1,8}
Output:
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
Constraints: 1 <= N <= 10^5
Solution: here
You are given a string S, the task is to reverse the string using stack.
https://www.geeksforgeeks.org/stack-set-3-reverse-string-using-stack/
Examples:
Input: S="GeeksforGeeks"
Output: skeeGrofskeeG
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints: 1 ≤ length of the string ≤ 100
Solution: here
The task is to find the next greater element for each element of the array in order of their appearance in the array.
https://www.geeksforgeeks.org/next-greater-element-in-same-order-as-input/
Examples:
Input:
N = 4, arr[] = [1 3 2 4]
Output:
3 4 4 -1
Explanation:
In the array, the next larger element
to 1 is 3 , 3 is 4 , 2 is 4 and for 4
since it doesn't exist, it is -1.
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1 ≤ N ≤ 10^6
1 ≤ Ai ≤ 10^18
Solution: here
Design a data-structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. Your task is to complete all the functions, using stack data-Structure.
https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
Examples:
Input:
Stack: 18 19 29 15 16
Output: 15
Explanation:
The minimum element of the stack is 15.
Expected Time Complexity : O(1) for all the 3 methods.
Expected Auixilliary Space : O(1) for all the 3 methods.
Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100
Solution: here
Given string S representing a postfix expression, the task is to evaluate the expression and find the final value. Operators will only include the basic arithmetic operators like *, /, + and -.
Examples:
Input: S = "231*+9-"
Output: -4
Explanation:
After solving the given expression,
we have -4 as result.
Expected Time Complexity: O(|S|)
Expected Auixilliary Space: O(|S|)
Constraints: 1 ≤ |S| ≤ 10^5
Solution: here
Given a binary matrix. Find the maximum area of a rectangle formed only of 1s in the given matrix.
Examples:
Input:
n = 4, m = 4
M[][] = {{0 1 1 0},
{1 1 1 1},
{1 1 1 1},
{1 1 0 0}}
Output: 8
Explanation: For the above test case the
matrix will look like
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
the max size rectangle is
1 1 1 1
1 1 1 1
and area is 4 * 2 = 8.
Expected Time Complexity : O(n*m)
Expected Auixiliary Space : O(m)
Constraints:
1<=n,m<=1000
0<=M[][]<=1
Solution: here
Given a stack, the task is to sort it such that the top of the stack has the greatest element.
https://www.geeksforgeeks.org/sort-a-stack-using-recursion/
Examples:
Input:
Stack: 3 2 1
Output: 3 2 1
Expected Time Complexity : O(N*N)v Expected Auixilliary Space : O(N) recursive.
Constraints: 1<=N<=100
Solution: here
Find the largest rectangular area possible in a given histogram where the largest rectangle can be
made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit.
https://www.geeksforgeeks.org/largest-rectangle-under-histogram/
Examples:
Input:
N = 8
arr[] = {7 2 8 9 1 3 6 5}
Output: 16
Explanation: Maximum size of the histogram
will be 8 and there will be 2 consecutive
histogram. And hence the area of the
histogram will be 8x2 = 16.
Expected Time Complxity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1 <= N <= 10^6
1 <= arr[i] <= 10^12
Solution: here
Given an expression string x. Examine whether the pairs and the orders of brackets are correct in exp.
https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/
Examples:
Input: exp = “[()]{}{()()}”
Output: Balanced
Time Complexity: O(n)
Auxiliary Space: O(n) for stack.
Constraints:
1 ≤ |x| ≤ 32000
Solution: here
Given an integer array. The task is to find the maximum of the minimum of every window size in the array.
https://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/
Examples:
Input: N = 7
arr[] = {10,20,30,50,10,70,30}
Output: 70 30 20 10 10 10 10
Expected Time Complxity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1 <= N <= 10^5
1 <= arr[i] <= 10^6
Solution: here
The stock span problem is a financial problem where we have a series of n daily price quotes
for a stock and we need to calculate the span of stock’s price for all n days.
The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days
just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.
For example, if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85},
then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}.
https://www.geeksforgeeks.org/the-stock-span-problem/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^5
1 ≤ C[i] ≤ 10^5
Solution: here
Given an infix expression in the form of string str. Convert this infix expression to postfix expression.
https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
Examples:
Input: str = "a+b*(c^d-e)^(f+gh)-i"
Output: abcd^e-fgh+^+i-
Explanation:
After converting the infix expression
into postfix expression, the resultant
expression will be abcd^e-fgh+^*+i-
Expected Time Complexity: O(|str|).
Expected Auxiliary Space: O(|str|).
Constraints: 1 ≤ |str| ≤ 10^5
Solution: here
Given a number N. The task is to generate and print all binary numbers with decimal values from 1 to N.
https://www.geeksforgeeks.org/interesting-method-generate-binary-numbers-1-n/
Examples:
Input:
N = 2
Output:
1 10
Explanation:
Binary numbers from
1 to 2 are 1 and 10.
Expected Time Complexity : O(N log2N)
Expected Auxilliary Space : O(N log2N)
Constraints: 1 ≤ N ≤ 10^6
Solution: here
Given an array arr[] of size N, enqueue the elements of the array into a queue and then dequeue them.
Expected time complexity: O(n)
Expected space complexity: O(n)
Constraints: 1 <= Ai <= 10^7
Solution: here
Implement a Stack using two queues q1 and q2.
https://www.geeksforgeeks.org/implement-stack-using-queue/
Examples:
Input:
push(2)
push(3)
pop()
push(4)
pop()
Output: 3 4
Expected Time Complexity: O(1) for push() and O(N) for pop() (or vice-versa).
Expected Auxiliary Space: O(1) for both push() and pop().
Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100
Solution: here
Given size of a queue and Q query. The task is to perform operations according to the type of query. Queries can be of following types: 1) 1 element: This means push the element into the queue (allowed only when queue is not full). 2) 2: This means pop the element at front from the queue (allowed only when queue is not empty).
Solution: here
Given an integer K and a queue of integers, we need to reverse the order of the first K elements of the queue, leaving the other elements in the same relative order.
Examples:
Input:
5 3
1 2 3 4 5
Output:
3 2 1 4 5
Expected TIme Complexity : O(n)
Expected Auxilliary Space : O(n)
Constraints:
1 <= N <= 1000
1 <= K <= N
Solution: here
Implement a Queue using 2 stacks s1 and s2 . https://www.geeksforgeeks.org/queue-using-stacks/
Expected Time Complexity : O(1) for push() and O(N) for pop() or O(N) for push() and O(1) for pop()
Expected Auxilliary Space : O(1).
Constraints:
1 <= Q <= 100
1 <= x <= 100
Solution: here
Given an array arr[] of size N and an integer K. Find the maximum for each and every contiguous subarray of size K.
https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/
Examples:
Input:
N = 9, K = 3
arr[] = 1 2 3 1 4 5 2 3 6
Output:
3 3 4 5 5 5 6
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^7
1 ≤ K ≤ N
0 ≤ arr[i] <= 10^7
Solution: here
Given a square chessboard of N x N size, the position of Knight and position of a target is given.
We need to find out the minimum steps a Knight will take to reach the target position.
https://www.geeksforgeeks.org/minimum-steps-reach-target-knight/
Expected Time Complexity: O(N2).
Expected Auxiliary Space: O(N2).
Constraints:
1 <= N <= 1000
1 <= Knight_pos(X, Y), Targer_pos(X, Y) <= N
Solution: here
Given two sorted arrays of distinct elements.
There is only 1 difference between the arrays.
First array has one element extra added in between.
Find the index of the extra element.
https://www.geeksforgeeks.org/find-index-of-an-extra-element-present-in-one-sorted-array/
Examples:
Input:
N = 6
A[] = {3,5,7,9,11,13}
B[] = {3,5,7,11,13}
Output: 3
Expected Time Complexity: O(log N). Expected Auxiliary Space: O(1).
Constraints: 2<=N<=10^4 1<=Ai<=10^5
Solution: here
Given a matrix mat[][] of n rows and m columns, consisting of 0’s and 1’s.
The task is to complete the function findPerimeter which returns an integer denoting the perimeter of sub-figures consisting of only 1’s in the matrix.
https://www.geeksforgeeks.org/find-perimeter-shapes-formed-1s-binary-matrix/
Examples:
Input : mat[][] =
{
1, 0,
1, 1,
}
Output : 8
Cell (1,0) and (1,1) making a L shape whose perimeter is 8.
Constraints:
1<=T<=100
1<=n, m<=20
Solution: here
Given two linked lists(can be sorted or unsorted) of size n1 and n2 of distinct elements. Given a value x.
The problem is to count all pairs from both lists whose sum is equal to the given value x.
Note: The pair has an element from each linked list.
https://www.geeksforgeeks.org/count-pairs-two-linked-lists-whose-sum-equal-given-value/
Examples:
Input : list1 = 3->1->5->7
list2 = 8->2->5->3
x = 10
Output : 2
The pairs are: (5, 5) and (7, 3)
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N+M)
Constraints:
1<=size of linked list<=10000
1<=X<=10000
Solution: here
Given a linked list, task is to make a function which check whether the length of linked list is even or odd.
https://www.geeksforgeeks.org/check-whether-the-length-of-given-linked-list-is-even-or-odd/
Examples:
Input : 1->2->3->4->NULL
Output : Even
Time Complexity: O(n)
Space Complexity: O(1)
Constraints:
1 <= T <= 100
1 <= N <= 10^3
1 <= A[i] <= 10^3
Solution: here
Given a string str and another string patt.
Find the character in patt that is present at the minimum index in str.
https://www.geeksforgeeks.org/find-character-first-string-present-minimum-index-second-string/
Examples:
Input: str = "zsyle", patt = "bjz"
Output: "z"
Expected Time Complexity: O(max(|str|, |patt|))
Expected Auxilary Space: O(K) where K <= 26
Constraints:
1 ≤ |str|, |patt| ≤ 10^4
Solution: here
Given a Binary Tree of size N , You have to count leaves in it.
https://www.geeksforgeeks.org/write-a-c-program-to-get-count-of-leaf-nodes-in-a-binary-tree/
Constraints:
1<= N <= 10^4
Solution: here
Given a Binary Tree, find Right view of it.
Right view of a Binary Tree is set of nodes visible when tree is viewed from right side.
https://www.geeksforgeeks.org/right-view-binary-tree-using-queue/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5
Solution: here
Given a Two Binary Trees, write a function that returns true if one is mirror of other, else returns false.
https://www.geeksforgeeks.org/check-if-two-trees-are-mirror/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes<= 10000
-1000 <= Data of a node<= 1000
Solution: here
Given a Binary Tree, find diameter of it.
The diameter of a tree is the number of nodes on the longest path between two end nodes in the tree.
https://www.geeksforgeeks.org/diameter-of-a-binary-tree/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 10000
1 <= Data of a node <= 1000
Solution: here
Given a Binary Tree, find diameter of it.
The diameter of a tree is the number of nodes on the longest path between two end nodes in the tree.
https://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of the Tree)
Constraints:
1 ≤ number of nodes ≤ 10^4
Solution: here
Write a function to print spiral order traversal of a tree.
https://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
0 <= Number of nodes <= 10^5
0 <= Data of a node <= 10^5
Solution: here
Given a Binary Tree. Find the Zig-Zag Level Order Traversal of the Binary Tree.
https://www.geeksforgeeks.org/zigzag-tree-traversal/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^4
Solution: here
Given a Binary Tree with all unique values and two nodes value n1 and n2.
The task is to find the lowest common ancestor of the given two nodes.
We may assume that either both n1 and n2 are present in the tree or none of them is present.
https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).
Note: H is the height of the tree.
Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5
Solution: here
Two trees are identical when they have same data and arrangement of data is also same.
https://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5
Solution: here
Given a binary tree and an integer S, check whether there is root to leaf path with its sum as S.
https://www.geeksforgeeks.org/root-to-leaf-path-sum-equal-to-a-given-number/
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 10^4
1 ≤ S ≤ 10^6
Solution: here
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines starting from left-most vertical line to right-most vertical line.
https://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1<=Number of nodes<=1000
Solution: here
Given a binary tree of size N, a node and a positive integer k., Your task is to complete the function kthAncestor(), the function should return the kth ancestor of the given node in the binary tree. If there does not exist any such ancestor then return -1.
https://www.geeksforgeeks.org/kth-ancestor-node-binary-tree-set-2/
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=N<=10^4
1<= K <= 100
Solution: here
Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e. by swapping left and right children of a number of nodes. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.
https://www.geeksforgeeks.org/tree-isomorphism-problem/
Expected Time Complexity: O(min(M, N)) where M and N are the sizes of the two trees.
Expected Auxiliary Space: O(min(H1, H2)) where H1 and H2 are the heights of the two trees.
Constraints:
1<=Number of nodes<=10^5
Solution: here
Given a binary tree, write a function that returns true if the tree satisfies below property.
For every node, data value must be equal to sum of data values in left and right children. Consider data value as 0 for NULL children.
https://www.geeksforgeeks.org/check-for-children-sum-property-in-a-binary-tree/
Expected Time Complexiy: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= N <= 10^5
1 <= Data on nodes <= 10^5
Solution: here
Given a binary tree and a key, insert the key into the binary tree at the first position available in level order.
https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/
Solution: here
Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom
(i.e. the deleted node is replaced by bottom most and rightmost node).
This is different from BST deletion.
Solution: here
Display preorder, postorder, inorder traversals of Binary Tree. (Recursive)
Solution: here
-
Given a binary tree, find its level order traversal. Level order traversal of a tree is breadth-first traversal for the tree.
Expected Time Complexity: O(N) Expected Auxiliary Space: O(N)
Constraints: 1 ≤ Number of nodes ≤ 10^5 1 ≤ Data of a node ≤ 10^5
Solution: here
-
Given a binary tree of size N, find its reverse level order traversal. ie- the traversal must begin from the last level.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)Constraints:
1 ≤ N ≤ 10^4Solution: here
-
Given a binary tree, find its height.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5Solution: here
-
Given a Binary Tree, find diameter of it. The diameter of a tree is the number of nodes on the longest path between two end nodes in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).Constraints:
1 <= Number of nodes <= 10000
1 <= Data of a node <= 1000Solution: here
-
Given a binary tree, the task is to create a new binary tree which is a mirror image of the given binary tree.
Solution: here
-
Inorder traversal recursive and iterative
Solution: here -
Preorder traversal recursive and iterative
Solution: here -
Postorder traversal recursive and iterative
Solution: here
-
Top view of Binary Tree
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)Constraints:
1 ≤ N ≤ 10^5
1 ≤ Node Data ≤ 10^5Solution: here
-
Bottom View of Binary Tree
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5Solution: here
-
Check for Balanced Tree
Constraints:
1 <= Number of nodes <= 10^5
0 <= Data of a node <= 10^6Expected time complexity: O(N)
Expected auxiliary space: O(h) , where h = height of treeSolution: here
-
ZigZag Tree Traversal
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)Constraints:
1 <= N <= 10^4Solution: here
Given a Binary Tree, print all diagonal elements in a binary tree belonging to the same line.
Time Complexity : O(N)
Space Complexity : O(N)
Constraints:
1 <= N <= 10^4
Solution: here
Given a Binary Tree, find its Boundary Traversal.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 ≤ Number of nodes ≤ 10^5
1 ≤ Data of a node ≤ 10^5
Solution: here
Construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure. Always start to construct the left child node of the parent first if it exists.
Solution: here
Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (leftmost node in BT) must be the head node of the DLL.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(H)
Note: H is the height of the tree and this space is used implicitly for recursion stack.
Constraints:
1 <= Number of nodes <= 10^5
1 <= Data of a node <= 10^5
Solution: here
Given a Binary Tree of size N , where each node can have positive or negative values. Convert this to a tree where each node contains the sum of the left and right sub trees of the original tree. The values of leaf nodes are changed to 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 10^4
Solution: here
Given 2 Arrays of Inorder and preorder traversal. Construct a tree and print the Postorder traversal.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N)
Constraints:
1<=Number of Nodes<=1000
Solution: here
Find the minimum number of swap required to convert it into Binary Search Tree.
Solution: here
Given a Binary Tree. Return 1 if, for every node X in the tree other than the leaves, its value is equal to the sum of its left subtree's value and its right subtree's value. Else return 0.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of the Tree)
Constraints:
1 ≤ number of nodes ≤ 10^4
Solution: here
-
Binary Search Tree (Search and Insertion)
Solution: here
-
Given an input stream of A of n characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream. If there is no such character then append '#' to the answer.
Expected Time Complexity: O(26 * n)
Expected Space Complexity: O(26)Constraints:
1 <= n <= 10^5Solution: here
-
N meetings in one room
There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting. What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time? Also note start time of one chosen meeting can't be equal to the end time of the other chosen meeting.Expected Time Complexity : O(N*LogN)
Expected Auxilliary Space : O(N)Constraints:
1 ≤ N ≤ 10^5
0 ≤ S[i] < F[i] ≤ 10^5Solution: here
-
Isomorphic Strings
Given two strings 'str1' and 'str2', check if these two strings are isomorphic to each other.Expected Time Complexity: O(|str1|+|str2|).
Expected Auxiliary Space: O(Number of different characters).
Note: |s| represents the length of string s.Constraints:
1 <= |str1|, |str2| <= 2*10^4Solution: here
-
Powers of 2
Given a non-negative integer N. The task is to check if N is a power of 2. More formally, check if N can be expressed as 2x for some x.Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).Constraints:
0 ≤ N ≤ 10^18Solution: here
-
Rat maze problem
Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.Expected Time Complexity: O((N^2)^4).
Expected Auxiliary Space: O(L * X), L = length of the path, X = number of paths.Constraints:
2 ≤ N ≤ 5
0 ≤ m[i][j] ≤ 1Solution: here
-
The celebrity problem
A celebrity is a person who is known to all but does not know anyone at a party. If you go to a party of N people, find if there is a celebrity in the party or not. A square NxN matrix M[][] is used to represent people at the party such that if an element of row i and column j is set to 1 it means ith person knows jth person. Here M[i][i] will always be 0.Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)Constraints:
2 <= N <= 3000
0 <= M[][] <= 1Solution: here
-
Aggressive cows
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Solution: here
Kadane's algorithm
Given an array arr of N integers. Find the contiguous sub-array with maximum sum.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^6
-107 ≤ A[i] ≤ 10^7
Solution: here
-
Implementing Max heap:
Given an array of N elements. The task is to build a Binary Heap from the given array. The heap can be either Max Heap or Min Heap.Solution: here
-
Heap sort:
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.Solution: here
Job Sequencing Problem
Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.
Solution: here
-
Huffman coding
Given a string S of distinct character of size N and their corresponding frequency f[ ] i.e. character S[i] has f[i] frequency. Your task is to build the Huffman tree print all the huffman codes in preorder traversal of the tree.Expected Time complexity: O(N * LogN)
Expected Space complexity: O(N)Constraints:
1 ≤ N ≤ 26Solution: here
-
Chocolate Distribution Problem
Given an array A[ ] of positive integers of size N, where each value represents the number of chocolates in a packet. Each packet can have a variable number of chocolates. There are M students, the task is to distribute chocolate packets among M students such that :- Each student gets exactly one packet.
- The difference between maximum number of chocolates given to a student and minimum number of chocolates given to a student is minimum.
Expected Time Complexity: O(N*Log(N))
Expected Auxiliary Space: O(1)Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 10^5
1 ≤ Ai ≤ 10^9
1 ≤ M ≤ NSolution: here
- Each student gets exactly one packet.
Number of 1 Bits
Given a positive integer N, print count of set bits in it.
Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^9
Solution: here
Non Repeating Numbers
Given an array A containing 2N+2 positive numbers, out of which 2N numbers exist in pairs whereas the other two number occur exactly once and are distinct. Find the other two numbers.
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
Constraints:
1 <= length of array <= 10^6
1 <= Elements in array <= 5 * 10^6
Solution: here
Dijkstra's Algorithm
Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.
Solution: here
Reverse a linked list
Solution: here
Median in a row-wise sorted Matrix
Given a row wise sorted matrix of size RxC where R and C are always odd, find the median of the matrix.
Expected Time Complexity: O(32 * R * log(C))
Expected Auxiliary Space: O(1)
Constraints:
1<= R,C <=150
1<= matrix[i][j] <=2000
Solution: here
Spirally traversing a matrix
Given a matrix of size r*c. Traverse the matrix in spiral form.
Expected Time Complexity: O(rc)
Expected Auxiliary Space: O(rc), for returning the answer only.
Constraints:
1 <= r, c <= 100
0 <= matrixi <= 100
Solution: here
Segregate even and odd nodes in a Linked List
Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 100
1 ≤ arr[i] ≤ 10000
Solution: here
Sliding Window Maximum (Maximum of all subarrays of size k)
Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.
Solution: here
Segregate even and odd nodes in a Linked List
Stickler the thief wants to loot money from a society having n houses in a single line. He is a weird person and follows a certain rule when looting the houses. According to the rule, he will never loot two consecutive houses. At the same time, he wants to maximize the amount he loots. The thief knows which house has what amount of money but is unable to come up with an optimal looting strategy. He asks for your help to find the maximum money he can get if he strictly follows the rule. Each house has a[i] amount of money present in it.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10000
1 ≤ arr[i] ≤ 10000
Solution: here
Merge K sorted linked lists
Given K sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list.
Expected Time Complexity: O(nk Logk)
Expected Auxiliary Space: O(k)
Constraints:
1 <= K <= 10^3
Solution: here
Kth largest element in BST
Given a Binary search tree. Your task is to complete the function which will return the Kth largest element without doing any modification in Binary Search Tree.
Expected Time Complexity: O(H + K)
Expected Auxiliary Space: O(H)
Constraints:
1 <= N <= 1000
1 <= K <= N
Solution: here
DFS of Graph
Given a connected undirected graph. Perform a Depth First Traversal of the graph.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
Constraints: 1 ≤ V, E ≤ 10^4
Solution: here