Sr. No.

Question
1 Find missing number in array 1 to n
2 Find duplicate number in array
3 Reverse array in-place
4 Reverse subarray between indices L and R
5 Find maximum and minimum element
6 Find second largest element
7 Move all zeros to end
8 Remove duplicates from sorted array
9 Check if array is sorted
10 Count frequency of each element
11 Rotate array by k steps
12 Rotate sorted array and detect pivot
13 Cyclically rotate array by one
14 Find rotation count in sorted rotated array
15 Check if arrays are rotations of each other
16 Rearrange positive negative alternately
17 Arrange so no identical adjacent
18 Sort array of 0s, 1s, 2s
19 Find majority element (¿n/2)
20 Find element occurring ¿n/3 times
21 Find first repeating element
22 Find first non-repeating element
23 Find kth largest element
24 Find peak element
25 Find all pairs with given sum
26 Count pairs with target sum
27 Pair with given difference
28 Find element that appears once (others twice)
29 Merge two sorted arrays
30 Union of two arrays without duplicates
31 Intersection of two arrays
32 Intersection of two sorted arrays
33 Common elements across three arrays
34 Minimum difference between any two elements
35 Prefix sum array construction
36 Range sum query using prefix sums
37 Find equilibrium index
38 Count inversions in array
39 Subarray with given sum
40 Subarray with sum divisible by k
41 Subarray with zero sum
42 Count subarrays with sum equal to k
43 Maximum sum contiguous subarray (Kadane)
44 Maximum product subarray
45 Maximum circular subarray sum
46 Longest increasing subsequence length
47 Longest bitonic subsequence
48 Sliding window maximum
49 Count distinct elements in each window of size k
50 Find smallest subarray with sum target
51 Smallest subarray to sort entire array
52 Largest subarray with equal 0s and 1s
53 Trapping rain water
54 Stock buy sell maximum profit (single transaction)
55 Stock buy sell maximum profit (multiple transactions)
56 Gas station tour problem
57 Minimum jumps to reach end
58 Minimum swaps to sort array
59 Largest sum with no adjacent elements
60 Maximum difference between two elements
61 Check if string is palindrome
62 Reverse a string
Sr. No. Question
63 Reverse words in a sentence
64 Reverse only vowels
65 Count vowels and consonants
66 Remove spaces from string
67 Remove extra spaces
68 Convert to uppercase/lowercase
69 Check if string contains only digits
70 Find length of string without strlen
71 Check if two strings are anagrams
72 Group anagrams together
73 Find first non-repeating character
74 First repeating character
75 Count occurrences of character
76 Sort characters by frequency
77 Check if string can be rearranged into palindrome
78 Most frequent element
79 Longest substring without repeating chars
80 Longest repeated non-overlapping substring
81 Longest common prefix among words
82 Longest common suffix among words
83 Count substrings starting and ending with same character
84 Smallest substring containing all characters of another
85 Find all substrings of a string
86 Substring search (implement strStr)
87 Find longest palindromic substring
88 Count palindromic substrings
89 Smallest palindrome by inserting characters
90 Shortest palindrome by prepending
91 Check if string has alternating vowel-consonant pattern
92 String compression (run-length encoding)
93 Remove adjacent duplicates until stable
94 Check if strings are rotations
95 Minimum rotations to match strings
96 Find lexicographically smallest rotation
97 Find lexicographically next permutation
98 Check if one string is subsequence of another
99 Minimum swaps to make strings identical
100 Check if two words can match by swapping two letters
101 Word break problem
102 Minimum window substring
103 Edit distance between strings
104 Regular expression matching
105 Count distinct subsequences
106 Keypad combinations from digits
107 Convert string to keypad digit sequence
108 Count distinct elements in array
109 Count frequency of words in sentence
110 Find element appearing exactly once
111 Find element appearing exactly twice
112 Find most frequent element
113 Group elements by frequency
114 Two sum using hashmap
115 Pair with given difference
116 Find subarray with zero sum
117 Longest subarray with sum k
118 Count subarrays with sum equal to k
119 Longest consecutive sequence
120 Largest subarray with equal 0s and 1s
121 Common elements across three arrays
122 Smallest subarray containing all distinct elements
123 Check if arrays are rotations of each other
124 Smallest range covering elements from k lists
Sr. No. Question
125 Prime number check
126 Generate primes up to n
127 Find nth prime number
128 Prime factorization of n
129 Check if number is power of 2
130 Check if number is power of 3
131 Count digits in number
132 Reverse digits of number
133 Check palindrome number
134 Check Armstrong number
135 Find GCD of two numbers
136 Find LCM of two numbers
137 Find LCM of array
138 Modular exponentiation
139 Factorial of number
140 Fibonacci sequence generation
141 Find all factors of n
142 Sum of divisors of n
143 Count composites in array
144 Fast exponentiation (power function)
145 Evaluate polynomial for given x
146 Identity matrix check
147 Transpose matrix
148 Rotate matrix 90°
149 Rotate matrix 180°
150 Find maximum element in matrix
151 Sum of diagonal elements
152 Check if matrix is symmetric
153 Spiral order traversal
154 Zigzag traversal
155 Search element in sorted matrix
156 Set row/column to zero if element zero
157 Count islands in binary matrix
158 Path existence in grid (DFS)
159 Largest rectangle of 1s in binary matrix
160 Count connected components
161 Word search in grid
162 Minimum path sum in matrix
163 Reverse linked list
164 Find middle of linked list
165 Detect cycle in linked list
166 Merge two sorted linked lists
167 Remove nth node from end
168 Remove duplicates from sorted list
169 Check if linked list is palindrome
170 Find intersection of two lists
171 Rotate linked list by k
172 Add two numbers as linked lists
173 Clone list with random pointers
174 Flatten a multilevel linked list
175 Check balanced parentheses
176 Evaluate postfix expression
177 Infix to postfix conversion
178 Reverse queue using stack
179 Implement circular queue
180 Next greater element
181 Stock span problem
182 Minimum stack with O(1) getMin
183 Interleave queue halves
184 Implement queue using stacks
185 Largest rectangle in histogram
186 Longest common subsequence
Sr. No. Question
187 Longest common substring
188 Minimum jumps to reach end
189 Coin change (minimum coins)
190 Maximum sum of non-adjacent elements
191 Palindrome partitioning minimum cuts
192 Find unique element (all others twice)
193 Find two unique elements
194 Find element where all others appear thrice
195 Count set bits in integer
196 Generate all subsets using bitmasks
197 BFS traversal of graph
198 DFS traversal of graph
199 Level order traversal of binary tree
200 Detect cycle in undirected graph
201 Find shortest path in unweighted graph
 1. Find Missing Number in Array

Problem Description
The problem requires finding a missing number in an array of integers from 1 to n. The array is 0-indexed, and the
missing number can be any integer between 1 and n (inclusive). The input is an array of integers, and the output is
the missing number. The array length will be n-1, where n is the maximum value that should be present in the
array.

Example
Consider an array of integers from 1 to 5: [1, 2, 4, 5]. The missing number is 3. For the array [1, 2, 3, 5], the
missing number is 4.

Solution
int n = arr . length + 1;
int expected sum = ( n ∗ ( n + 1 ) ) / 2 ;
int actual sum = 0;
for ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
a c t u a l s u m += a r r [ i ] ;
}
i n t missing number = expected sum − a c t u a l s u m ;
r e t u r n missing number ;

””
 2. Find Duplicate Number in Array

Problem Description
The problem requires finding a duplicate number in an array of integers. The array contains n + 1 integers, where
each integer is between 1 and n (inclusive). There is only one duplicate number in the array. The algorithm should
take the array as input and return the duplicate number. The input array is not sorted, and the algorithm should
have a time complexity of O(n) and a space complexity of O(1) for the optimal solution.

Example
The input array is [1, 3, 4, 2, 2]. The expected output is 2, which is the duplicate number in the array. Another
example is the input array [3, 1, 3, 4, 2], where the expected output is 3.

Solution
int findDuplicate = 0;
i n t t o r t o i s e = nums [ 0 ] ;
i n t h a r e = nums [ 0 ] ;
do {
t o r t o i s e = nums [ t o r t o i s e ] ;
h a r e = nums [ nums [ h a r e ] ] ;
} w h i l e ( t o r t o i s e != h a r e ) ;
t o r t o i s e = nums [ 0 ] ;
w h i l e ( t o r t o i s e != h a r e ) {
t o r t o i s e = nums [ t o r t o i s e ] ;
h a r e = nums [ h a r e ] ;
}
f i n d D u p l i c a t e = hare ;

””
 3. Reverse Array In-Place

Problem Description
The problem requires reversing an array in-place, meaning that the reversal should be done without using any
additional storage space that scales with the input size. The input is an array of integers, and the output should be
the reversed array. The algorithm should be efficient and scalable.

Example
For example, given the input array [1, 2, 3, 4, 5], the expected output is [5, 4, 3, 2, 1]. Another example is the input
array [10, 20, 30], which should be reversed to [30, 20, 10].

Solution
int l e f t = 0;
int right = arr . length − 1;
while ( l e f t < right ) {
i n t temp = a r r [ l e f t ] ;
arr [ l e f t ] = arr [ right ] ;
a r r [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}

””
 4. Reverse Subarray Between Indices

Problem Description
The problem requires reversing a subarray within a given array between indices L and R. The input is an array of
integers and two indices L and R. The output is the modified array with the subarray between indices L and R
reversed. The algorithm should be efficient and scalable.

Example
For the input array [1, 2, 3, 4, 5] and indices L = 1, R = 3, the expected output is [1, 4, 3, 2, 5]. The subarray
between indices 1 and 3 is [2, 3, 4], which is reversed to [4, 3, 2].

Solution
i n t [ ] a r r = new i n t [ ] { 1 , 2 , 3 , 4 , 5 } ;
int L = 1;
int R = 3;
int l e f t = L;
i n t r i g h t = R;
while ( l e f t < right ) {
i n t temp = a r r [ l e f t ] ;
arr [ l e f t ] = arr [ right ] ;
a r r [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}

””
 5. Find Maximum and Minimum Element

Problem Description
The problem requires finding the maximum and minimum element in an array of integers. The input is an array of
integers and the output should be the maximum and minimum element. The algorithm should have a time
complexity of O(n) where n is the number of elements in the array.

Example
For the input array [5, 2, 8, 12, 3], the expected output is maximum = 12 and minimum = 2.

Solution
i n t maxElement = a r r a y [ 0 ] ;
i n t minElement = a r r a y [ 0 ] ;
f o r ( i n t i = 1 ; i < a r r a y . l e n g t h ; i ++) {
i f ( a r r a y [ i ] > maxElement ) {
maxElement = a r r a y [ i ] ;
}
i f ( a r r a y [ i ] < minElement ) {
minElement = a r r a y [ i ] ;
}
}
System . out . p r i n t l n ( ” ”Maximum e l e m e n t : ” ” + maxElement ) ;
System . out . p r i n t l n ( ” ”Minimum e l e m e n t : ” ” + minElement ) ;

””
 6. Second Largest Element

Problem Description
The problem requires finding the second largest element in an array of integers. The input is an array of integers
and the output is the second largest element. If no second largest element exists, the output should be a message
indicating this.

Example
For the input array [10, 20, 4, 45, 99], the output should be 45. For the input array [1, 1, 1, 1], the output should be
a message indicating that no second largest element exists.

Solution
i n t l a r g e s t = I n t e g e r . MIN VALUE ;
i n t s e c o n d l a r g e s t = I n t e g e r . MIN VALUE ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
i f ( arr [ i ] > largest ) {
second largest = largest ;
largest = arr [ i ] ;
} e l s e i f ( a r r [ i ] > s e c o n d l a r g e s t && a r r [ i ] != l a r g e s t ) {
second largest = arr [ i ] ;
}
}
i f ( s e c o n d l a r g e s t == I n t e g e r . MIN VALUE) {
System . out . p r i n t l n ( ” ”No s e c o n d l a r g e s t e l e m e n t e x i s t s ” ” ) ;
} else {
System . out . p r i n t l n ( s e c o n d l a r g e s t ) ;
}

””
 7. Move Zeros to End

Problem Description
Move all zeros to the end of an array, maintaining the relative order of non-zero elements. The input is an array of
integers, and the output is the modified array with all zeros at the end.

Example
Input: [0, 1, 0, 3, 12] Output: [1, 3, 12, 0, 0]

Solution
i n t [ ] moveZeros ( i n t [ ] a r r ) {
i n t nonZeroPos = 0 ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
i f ( a r r [ i ] != 0 ) {
i n t temp = a r r [ nonZeroPos ] ;
a r r [ nonZeroPos ] = a r r [ i ] ;
a r r [ i ] = temp ;
nonZeroPos++;
}
}
return arr ;
}

””
 8. Remove Duplicates from Sorted Array

Problem Description
Remove duplicates from a sorted array in-place, returning the length of the new array without duplicates. The
input is a sorted array of integers, and the output should be the length of the array after removing duplicates. The
array should be modified in-place.

Example
Input: nums = [1, 1, 2, 2, 3, 4, 4, 5] Output: length = 5, nums = [1, 2, 3, 4, 5]

Solution
int i = 0;
f o r ( i n t j = 1 ; j < nums . l e n g t h ; j ++) {
i f ( nums [ j ] != nums [ i ] ) {
i ++;
nums [ i ] = nums [ j ] ;
}
}
return i + 1;

””
 9. Check if Array is Sorted

Problem Description
Check if the given array is sorted in ascending order. The array is considered sorted if each element is less than or
equal to the next element. The input is an array of integers and the output is a boolean value indicating whether
the array is sorted or not.

Example
Input array: [1, 2, 3, 4, 5] Expected output: true Input array: [5, 4, 3, 2, 1] Expected output: false

Solution
int n = array . length ;
boolean i s S o r t e d = true ;
f o r ( i n t i = 0 ; i < n − 1 ; i ++) {
i f ( array [ i ] > array [ i + 1 ] ) {
isSorted = false ;
break ;
}
}
return isSorted ;

””
 10. Element Frequency Counter

Problem Description
The element frequency counter algorithm is designed to count the frequency of each element in a given array or list
of elements. The input to this algorithm is an array of integers, and the output is a data structure containing the
frequency of each element. The algorithm should be able to handle duplicate elements and report their frequencies
accurately.

Example
For the input array [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], the expected output is a data structure showing that element 1
appears once, element 2 appears twice, element 3 appears three times, and element 4 appears four times.

Solution
i n t [ ] arr = {1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4};
i n t [ ] f r e q = new i n t [ 1 0 0 0 ] ; // assuming e l e m e n t s a r e w i t h i n
range 0 t o 999
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
f r e q [ arr [ i ]]++;
}
f o r ( i n t i = 0 ; i < f r e q . l e n g t h ; i ++) {
i f ( f r e q [ i ] > 0) {
System . out . p r i n t l n ( ” ” Element ” ” + i + ” ” a p p e a r s ” ” +
f r e q [ i ] + ”” times ”” ) ;
}
}

””
 11. Rotate Array by K Steps

Problem Description
The problem requires rotating an array by k steps. The array is rotated to the right, meaning each element is
shifted k positions to the right, wrapping around to the start of the array when necessary. The input is an array of
integers and an integer k, and the output is the rotated array. The array can contain duplicate elements and can be
of any size.

Example
For example, given the array [1, 2, 3, 4, 5, 6, 7] and k = 3, the output would be [5, 6, 7, 1, 2, 3, 4]. Another example
is the array [1, 2, 3, 4, 5] with k = 2, resulting in [4, 5, 1, 2, 3].

Solution
i n t [ ] nums = new i n t [ ] { 1 , 2 , 3 , 4 , 5 , 6 , 7 } ;
int k = 3;
k = k % nums . l e n g t h ;
i n t [ ] r e s u l t = new i n t [ nums . l e n g t h ] ;
f o r ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {
r e s u l t [ ( i + k ) % nums . l e n g t h ] = nums [ i ] ;
}
f o r ( i n t i = 0 ; i < r e s u l t . l e n g t h ; i ++) {
nums [ i ] = r e s u l t [ i ] ;
}
// A l t e r n a t i v e l y , u s i n g r e v e r s e approach
// r e v e r s e ( nums , 0 , nums . l e n g t h − 1) ;
// r e v e r s e ( nums , 0 , k − 1) ;
// r e v e r s e ( nums , k , nums . l e n g t h − 1) ;
// where r e v e r s e f u n c t i o n i s d e f i n e d as
// p u b l i c v o i d r e v e r s e ( i n t [ ] nums , i n t s t a r t , i n t end ) {
// w h i l e ( s t a r t < end ) {
// i n t temp = nums [ s t a r t ] ;
// nums [ s t a r t ] = nums [ end ] ;
// nums [ end ] = temp ;
// s t a r t ++;
// end −−;
// }
// }

””
 12. Rotate Sorted Array and Detect Pivot

Problem Description
The problem requires finding the pivot element in a rotated sorted array. A rotated sorted array is an array that
was initially sorted in ascending order, but then its elements were rotated some number of times. The input is a
rotated sorted array, and the output should be the index of the pivot element, which is the smallest element in the
array. The array does not contain duplicate elements.

Example
Consider the rotated sorted array [4, 5, 6, 7, 0, 1, 2]. The output should be 4, which is the index of the pivot
element 0. Another example is the array [3, 4, 5, 1, 2], where the output should be 3, which is the index of the pivot
element 1.

Solution
int l e f t = 0;
i n t r i g h t = nums . l e n g t h − 1 ;
while ( l e f t < right ) {
i n t mid = l e f t + ( r i g h t − l e f t ) / 2 ;
i f ( nums [ mid ] > nums [ r i g h t ] ) {
l e f t = mid + 1 ;
} else {
r i g h t = mid ;
}
}
return l e f t ;

””
 13. Cyclic Array Rotation

Problem Description
The problem requires cyclically rotating an array by one position. The array is rotated in a cyclic manner, meaning
the last element becomes the first element, and all other elements shift one position to the right. The input is an
array of integers, and the output is the rotated array.

Example
For the input array [1, 2, 3, 4, 5], the expected output is [5, 1, 2, 3, 4]. This is because the last element (5) becomes
the first element, and all other elements shift one position to the right.

Solution
i n t temp = a r r [ a r r . l e n g t h − 1 ] ;
f o r ( i n t i = a r r . l e n g t h − 1 ; i > 0 ; i −−) {
arr [ i ] = arr [ i − 1 ] ;
}
a r r [ 0 ] = temp ;

””
14. Rotation Count in Sorted Rotated Array

Problem Description
The problem requires finding the rotation count in a sorted rotated array. The array is sorted in ascending order,
but it has been rotated an unknown number of times. The input is a sorted rotated array, and the output is the
rotation count. The array does not contain duplicate elements.

Example
For the input array [11, 12, 15, 18, 2, 5, 6, 8], the output is 4, because the array has been rotated 4 times. For the
input array [1, 2, 3, 4, 5], the output is 0, because the array has not been rotated.

Solution
i n t low = 0 ;
i n t high = arr . length − 1 ;
w h i l e ( low < h i g h ) {
i n t mid = low + ( h i g h − low ) / 2 ;
i f ( a r r [ mid ] > a r r [ h i g h ] ) {
low = mid + 1 ;
} else {
h i g h = mid ;
}
}
r e t u r n low ;

””
 15. Array Rotation Check

Problem Description
Check if two given arrays are rotations of each other. Given two arrays, arr1 and arr2, of size n, determine if arr2 is
a rotation of arr1. The input consists of two arrays of integers, and the output is a boolean value indicating whether
arr2 is a rotation of arr1.

Example
Consider two arrays: arr1 = [1, 2, 3, 4, 5] and arr2 = [3, 4, 5, 1, 2]. The expected output is true, as arr2 is a
rotation of arr1.

Solution
i n t [ ] arr1 = {1 , 2 , 3 , 4 , 5};
i n t [ ] arr2 = {3 , 4 , 5 , 1 , 2};
int n = arr1 . length ;
boolean isRotation = f a l s e ;

i n t [ ] c o n c a t A r r = new i n t [ 2 ∗ n ] ;
f o r ( i n t i = 0 ; i < n ; i ++) {
concatArr [ i ] = arr1 [ i ] ;
concatArr [ i + n ] = arr1 [ i ] ;
}

f o r ( i n t i = 0 ; i < n ; i ++) {
b o o l e a n match = t r u e ;
f o r ( i n t j = 0 ; j < n ; j ++) {
i f ( c o n c a t A r r [ i + j ] != a r r 2 [ j ] ) {
match = f a l s e ;
break ;
}
}
i f ( match ) {
isRotation = true ;
break ;
}
}

i f ( isRotation ) {
System . out . p r i n t l n ( ” ” t r u e ” ” ) ;
} else {
System . out . p r i n t l n ( ” ” f a l s e ” ” ) ;
}

””
 16. Rearrange Positive Negative Alternately

Problem Description
The goal is to rearrange the elements of an array such that all positive numbers are followed by a negative number
and vice versa. The array contains both positive and negative integers. The input array is expected to have enough
elements to allow for this rearrangement. The output should be the rearranged array.

Example
Input array: [1, -2, 3, -4, 5, -6] Expected output: [1, -2, 3, -4, 5, -6] Another example: Input array: [-1, 2, -3, 4, -5,
6] Expected output: [2, -1, 4, -3, 6, -5]

Solution
pos = [ ]
neg = [ ]
f o r num i n a r r :
i f num > 0 :
pos . append (num)
else :
neg . append (num)
i = j = 0
f o r k in range ( len ( arr ) ) :
i f k % 2 == 0 :
a r r [ k ] = pos [ i ]
i += 1
else :
a r r [ k ] = neg [ j ]
j += 1

””
 17. Arrange Without Identical Adjacents

Problem Description
The goal is to rearrange elements in a given array such that no two identical elements are adjacent to each other.
The input is an array of characters or integers, and the output should be the rearranged array. The approach
involves sorting the array first and then placing elements alternately to ensure no identical elements are adjacent.

Example
Consider an input array [a, a, b, b, c, c]. After sorting, it becomes [a, a, b, b, c, c]. The expected output could be
[a, b, a, b, c, c] or any other valid arrangement where no two identical elements are adjacent.

Solution
// I n i t i a l i z e v a r i a b l e s
c h a r [ ] a r r = new c h a r [ ] { ’ a ’ , ’ a ’ , ’ b ’ , ’ b ’ , ’ c ’ , ’ c ’ } ;
int n = arr . length ;

// S o r t t h e a r r a y
f o r ( i n t i = 0 ; i < n − 1 ; i ++) {
f o r ( i n t j = i + 1 ; j < n ; j ++) {
i f ( arr [ i ] > arr [ j ] ) {
c h a r temp = a r r [ i ] ;
arr [ i ] = arr [ j ] ;
a r r [ j ] = temp ;
}
}
}

// I n i t i a l i z e two p o i n t e r s
int i = 0;
int j = 1;

// I n i t i a l i z e r e s u l t a r r a y
c h a r [ ] r e s u l t = new c h a r [ n ] ;

// P l a c e e l e m e n t s a l t e r n a t e l y
i n t index = 0 ;
w h i l e ( i < n && j < n ) {
r e s u l t [ i n d e x++] = a r r [ i ] ;
r e s u l t [ i n d e x++] = a r r [ j ] ;
i ++;
j ++;
}

// I f t h e r e a r e remain ing e l e m e n t s , append them

while ( i < n) {
r e s u l t [ i n d e x++] = a r r [ i ] ;
 i ++;
}
while ( j < n) {
r e s u l t [ i n d e x++] = a r r [ j ] ;
j ++;
}

””
 18. Sort Array of 0s, 1s, 2s

Problem Description
Sort an array of 0s, 1s, and 2s. The input array contains only these three integers, and the task is to sort this array
in ascending order. The input is an array of integers, and the output should be the sorted array. The algorithm
should have a time complexity of O(n) and a space complexity of O(1), where n is the number of elements in the
array.

Example
Consider the input array [0, 1, 2, 0, 1, 2]. The expected output is [0, 0, 1, 1, 2, 2]. Another example is the input
array [2, 0, 1], and the expected output is [0, 1, 2].

Solution
i n t low = 0 ;
i n t mid = 0 ;
i n t high = arr . length − 1 ;

w h i l e ( mid <= h i g h ) {
i f ( a r r [ mid ] == 0 ) {
i n t temp = a r r [ low ] ;
a r r [ low ] = a r r [ mid ] ;
a r r [ mid ] = temp ;
low++;
mid++;
} e l s e i f ( a r r [ mid ] == 1 ) {
mid++;
} else {
i n t temp = a r r [ mid ] ;
a r r [ mid ] = a r r [ h i g h ] ;
a r r [ h i g h ] = temp ;
high −−;
}
}

””
 19. Boyer-Moore Majority Vote Algorithm

Problem Description
The Boyer-Moore Majority Vote algorithm is used to find the majority element in an array, which is the element
that appears more than n/2 times. The input is an array of integers, and the output is the majority element if it
exists. The algorithm works by essentially maintaining a counter for the majority element. It increments the
counter when it sees the majority element and decrements it when it sees a different element. If the counter
becomes zero, the algorithm sets the current element as the majority element.

Example
For the input array [3, 3, 4, 2, 3, 3, 2, 3, 3], the output will be 3 because it appears more than n/2 times. For the
input array [1, 2, 3, 4], there is no majority element.

Solution
i n t count = 0 ;
int candidate = 0;
f o r ( i n t num : nums ) {
i f ( count == 0 ) {
c a n d i d a t e = num ;
count = 1 ;
} e l s e i f ( c a n d i d a t e == num) {
count += 1 ;
} else {
count −= 1 ;
}
}
int occurrences = 0;
f o r ( i n t num : nums ) {
i f (num == c a n d i d a t e ) {
o c c u r r e n c e s += 1 ;
}
}
i f ( o c c u r r e n c e s > nums . l e n g t h / 2 ) {
return candidate ;
} else {
r e t u r n −1; // or any o t h e r v a l u e t o i n d i c a t e no m a j o r i t y
element
}

””
 20. Find Element Occurring More Than n/3
Times

Problem Description
The problem requires finding an element that occurs more than n/3 times in an array of size n. The input is an
array of integers and the output should be the elements that occur more than n/3 times. If no such element exists,
the output can be an empty list or a message indicating that no such element was found.

Example
For the input array [3, 2, 3, 2, 2, 3, 3], the expected output would be [3, 2] because both 3 and 2 occur more than
n/3 times. For the input array [1, 2, 3, 4, 5], the expected output would be an empty list or a message indicating
that no such element was found.

Solution
i n t count1 = 0 , count2 = 0 ;
int candidate1 = 0 , candidate2 = 1;
f o r ( i n t num : nums ) {
i f (num == c a n d i d a t e 1 ) {
count1++;
} e l s e i f (num == c a n d i d a t e 2 ) {
count2++;
} e l s e i f ( count1 == 0 ) {
c a n d i d a t e 1 = num ;
count1 = 1 ;
} e l s e i f ( count2 == 0 ) {
c a n d i d a t e 2 = num ;
count2 = 1 ;
} else {
count1 −−;
count2 −−;
}
}
count1 = 0 ; count2 = 0 ;
f o r ( i n t num : nums ) {
i f (num == c a n d i d a t e 1 ) count1++;
e l s e i f (num == c a n d i d a t e 2 ) count2++;
}
i f ( count1 > nums . l e n g t h / 3 ) r e s u l t . add ( c a n d i d a t e 1 ) ;
i f ( count2 > nums . l e n g t h / 3 ) r e s u l t . add ( c a n d i d a t e 2 ) ;

””
 21. Find First Repeating Element

Problem Description
Find the first repeating element in an array of integers. The input is an array of integers and the output is the first
repeating element. If no repeating element is found, return -1. The array can contain duplicate elements and the
input array is not sorted.

Example
Input array: [2, 3, 5, 2, 7, 8, 3] Expected output: 2 Explanation: The first repeating element in the array is 2.

Solution
i n t [ ] a r r = new i n t [ ] { 2 , 3 , 5 , 2 , 7 , 8 , 3 } ;
int n = arr . length ;
HashMap<I n t e g e r , I n t e g e r > map = new HashMap<>() ;
i n t f i r s t R e p e a t i n g = −1;

f o r ( i n t i = 0 ; i < n ; i ++) {
i f (map . c o n t a i n s K e y ( a r r [ i ] ) ) {
firstRepeating = arr [ i ] ;
break ;
} else {
map . put ( a r r [ i ] , i ) ;
}
}

System . out . p r i n t l n ( f i r s t R e p e a t i n g ) ;

””
 22. Find First Non-Repeating Element

Problem Description
The problem requires finding the first non-repeating element in a given array of integers. The input is an array of
integers and the output should be the first non-repeating element. If no such element exists, the output can be a
special value such as -1 or null. The algorithm should have a time complexity of O(n) and a space complexity of
O(n), where n is the number of elements in the array.

Example
Consider the input array [2, 3, 5, 4, 5, 3, 4]. The expected output is 2 because it is the first non-repeating element
in the array.

Solution
i n t [ ] a r r = new i n t [ ] { 2 , 3 , 5 , 4 , 5 , 3 , 4 } ;
int n = arr . length ;
i n t [ ] f r e q = new i n t [ 1 0 0 0 ] ; // assuming e l e m e n t s a r e i n range
0−999

f o r ( i n t i = 0 ; i < n ; i ++) {
f r e q [ arr [ i ]]++;
}

f o r ( i n t i = 0 ; i < n ; i ++) {
i f ( f r e q [ a r r [ i ] ] == 1 ) {
System . out . p r i n t l n ( a r r [ i ] ) ;
break ;
}
}

””
 23. Kth Largest Element

Problem Description
The kth largest element in an unsorted array can be found using the QuickSelect algorithm or by maintaining a
Min-Heap of size k. The input to the algorithm is an array of integers and an integer k, where 1 ¡= k ¡= n and n is
the number of elements in the array. The output is the kth largest element in the array. The algorithm should have
a time complexity of O(n) on average for QuickSelect or O(n log k) for the Min-Heap approach.

Example
For the input array [3, 2, 1, 5, 6, 4] and k = 2, the output should be 5, which is the 2nd largest element in the array.
For the input array [10, 4, 5, 8, 6, 11, 26] and k = 3, the output should be 10, which is the 3rd largest element in
the array.

Solution
i n t [ ] nums = new i n t [ ] { 3 , 2 , 1 , 5 , 6 , 4 } ;
int k = 2;
int l e f t = 0;
i n t r i g h t = nums . l e n g t h − 1 ;
w h i l e ( l e f t <= r i g h t ) {
i n t p i v o t I n d e x = p a r t i t i o n ( nums , l e f t , r i g h t ) ;
i f ( p i v o t I n d e x == nums . l e n g t h − k ) {
System . out . p r i n t l n ( nums [ p i v o t I n d e x ] ) ;
break ;
} e l s e i f ( p i v o t I n d e x < nums . l e n g t h − k ) {
l e f t = pivotIndex + 1;
} else {
right = pivotIndex − 1;
}
}

i n t p a r t i t i o n ( i n t [ ] nums , i n t l e f t , i n t r i g h t ) {
i n t p i v o t = nums [ r i g h t ] ;
int i = l e f t − 1;
f o r ( i n t j = l e f t ; j < r i g h t ; j ++) {
i f ( nums [ j ] > p i v o t ) {
i ++;
i n t temp = nums [ i ] ;
nums [ i ] = nums [ j ] ;
nums [ j ] = temp ;
}
}
i n t temp = nums [ i + 1 ] ;
nums [ i + 1 ] = nums [ r i g h t ] ;
nums [ r i g h t ] = temp ;
return i + 1;
}
””
 24. Find Peak Element

Problem Description
Find peak element in an array using binary search approach. The peak element is the element which is not smaller
than its neighbors. Given an array of integers, find a peak element in it. A peak element is an element that is not
smaller than its neighbors. For input arr = [1, 2, 3, 1], the output should be 3. The input array may contain
duplicate elements. If there are multiple peak elements, the algorithm should return any one of them.

Example
For the input array arr = [1, 2, 3, 1], the expected output is 3. For the input array arr = [1, 3, 20, 4, 1, 0], the
expected output is 20.

Solution
i n t low = 0 ;
i n t high = arr . length − 1 ;
w h i l e ( low <= h i g h ) {
i n t mid = low + ( h i g h − low ) / 2 ;
i f ( ( mid == 0 | | a r r [ mid ] >= a r r [ mid −1]) && ( mid == a r r .
l e n g t h − 1 | | a r r [ mid ] >= a r r [ mid +1]) ) {
r e s u l t = a r r [ mid ] ;
break ;
} e l s e i f ( mid < a r r . l e n g t h − 1 && a r r [ mid ] < a r r [ mid +1]) {
low = mid + 1 ;
} else {
h i g h = mid − 1 ;
}
}
r e s u l t = a r r [ low ] ;

””
 25. Find All Pairs With Given Sum

Problem Description
Find all pairs of elements in an array that add up to a given sum. The input is an array of integers and a target
sum, and the output is a list of pairs of elements that add up to the target sum.

Example
Input array: [1, 2, 3, 4, 5], target sum: 7 Expected output: [(2, 5), (3, 4)]

Solution
i n t [ ] arr = {1 , 2 , 3 , 4 , 5};
i n t targetSum = 7 ;
j a v a . u t i l . Arrays . s o r t ( a r r ) ;
int l e f t = 0;
int right = arr . length − 1;
while ( l e f t < right ) {
i n t currentSum = a r r [ l e f t ] + a r r [ r i g h t ] ;
i f ( currentSum == targetSum ) {
System . out . p r i n t l n ( ” ” ( ” ” + a r r [ l e f t ] + ” ” , ” ” + a r r [
r i g h t ] + ”” ) ”” ) ;
l e f t ++;
r i g h t −−;
} e l s e i f ( currentSum < targetSum ) {
l e f t ++;
} else {
r i g h t −−;
}
}

””
 26. Count Pairs with Target Sum

Problem Description
The problem requires counting the number of pairs in an array that sum up to a given target value. The input is an
array of integers and a target sum, and the output is the count of pairs that sum up to the target. The array can
contain duplicate elements, and each element can be part of multiple pairs.

Example
For the input array [1, 2, 3, 4, 5] and target sum 7, the expected output is 2 because there are two pairs (2, 5) and
(3, 4) that sum up to 7.

Solution
int countPairs = 0;
HashMap<I n t e g e r , I n t e g e r > freqMap = new HashMap<>() ;
f o r ( i n t num : nums ) {
i n t complement = t a r g e t − num ;
i f ( freqMap . c o n t a i n s K e y ( complement ) ) {
c o u n t P a i r s += freqMap . g e t ( complement ) ;
}
freqMap . put (num , freqMap . g e t O r D e f a u l t (num , 0 ) + 1 ) ;
}
return countPairs ;

””
 27. Pair with given difference

Problem Description
The problem requires finding a pair of elements in an array that have a given difference. The input is an array of
integers and a target difference, and the output is a pair of integers that have the given difference. The array can
contain duplicate elements, and the pair can be in any order.

Example
For example, given the array [1, 7, 5, 9, 2] and a target difference of 3, the output would be (2, 5) or (5, 2) or (1, 4)
is not possible as 4 is not in array, but (7, 4) is not possible as 4 is not in array, but (1, 4) is not possible as 4 is not
in array, actual output is (2, 5).

Solution
i n t [ ] nums = new i n t [ ] { 1 , 7 , 5 , 9 , 2 } ;
int d i f f = 3;
Map<I n t e g e r , I n t e g e r > map = new HashMap<>() ;
f o r ( i n t num : nums ) {
i f (map . c o n t a i n s K e y (num − d i f f ) ) {
System . out . p r i n t l n ( ” ” P a i r with g i v e n difference : (”
” + (num − d i f f ) + ” ” , ” ” + num + ”” ) ”” ) ;
break ;
}
i f (map . c o n t a i n s K e y (num + d i f f ) ) {
System . out . p r i n t l n ( ” ” P a i r with g i v e n difference : (”
” + num + ” ” , ” ” + (num + d i f f ) + ”” ) ”” ) ;
break ;
}
map . put (num , num) ;
}

””
 28. Single Number

Problem Description
The problem requires finding an element that appears once in an array where all other elements appear twice. The
input is an array of integers and the output is the single number that appears only once. The array can contain
duplicate elements and the single number can be any integer.

Example
The input array can be [2, 2, 1] and the expected output is 1. Another example is [4, 1, 2, 1, 2] where the output is
4.

Solution
i n t singleNumber = 0 ;
f o r ( i n t num : nums ) {
singleNumber ˆ= num ;
}
r e t u r n singleNumber ;

””
 29. Merge Two Sorted Arrays

Problem Description
Merge two sorted arrays into one sorted array. The input consists of two sorted arrays, and the output should be a
new sorted array containing all elements from both input arrays.

Example
Sample input: array1 = [1, 3, 5], array2 = [2, 4, 6] Expected output: [1, 2, 3, 4, 5, 6]

Solution
i n t [ ] array1 = {1 , 3 , 5};
i n t [ ] array2 = {2 , 4 , 6};
i n t [ ] r e s u l t = new i n t [ a r r a y 1 . l e n g t h + a r r a y 2 . l e n g t h ] ;
int i = 0 , j = 0 , k = 0;
w h i l e ( i < a r r a y 1 . l e n g t h && j < a r r a y 2 . l e n g t h ) {
i f ( array1 [ i ] < array2 [ j ] ) {
r e s u l t [ k++] = a r r a y 1 [ i ++];
} else {
r e s u l t [ k++] = a r r a y 2 [ j ++];
}
}
while ( i < array1 . length ) {
r e s u l t [ k++] = a r r a y 1 [ i ++];
}
while ( j < array2 . length ) {
r e s u l t [ k++] = a r r a y 2 [ j ++];
}

””
30. Union of Two Arrays Without Duplicates

Problem Description
The problem requires finding the union of two arrays without duplicates. Given two arrays, the task is to return an
array containing all unique elements from both arrays. The input consists of two integer arrays, and the output
should be an array of integers representing the union of the input arrays without duplicates.

Example
Consider two input arrays: [1, 2, 3, 4, 5] and [4, 5, 6, 7, 8]. The expected output would be [1, 2, 3, 4, 5, 6, 7, 8],
which represents the union of the two input arrays without duplicates.

Solution
Set<I n t e g e r > s e t = new HashSet <>() ;
i n t [ ] arr1 = {1 , 2 , 3 , 4 , 5};
i n t [ ] arr2 = {4 , 5 , 6 , 7 , 8};
f o r ( i n t num : a r r 1 ) {
s e t . add (num) ;
}
f o r ( i n t num : a r r 2 ) {
s e t . add (num) ;
}
I n t e g e r [ ] r e s u l t = s e t . toArray ( new I n t e g e r [ 0 ] ) ;

””
 31. Intersection of Two Arrays

Problem Description
The intersection of two arrays contains all unique elements that are present in both arrays. Given two arrays, find
their intersection. The input consists of two arrays, and the output should be an array containing the intersection
of the input arrays.

Example
Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2] Output: [2] Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4] Output: [4,
9]

Solution
i n t [ ] nums1 = { 1 , 2 , 2 , 1 } ;
i n t [ ] nums2 = { 2 , 2 } ;
Arrays . s o r t ( nums1 ) ;
Arrays . s o r t ( nums2 ) ;
int i = 0 , j = 0;
L i s t <I n t e g e r > r e s u l t = new A r r a y L i s t <>() ;
w h i l e ( i < nums1 . l e n g t h && j < nums2 . l e n g t h ) {
i f ( nums1 [ i ] < nums2 [ j ] ) {
i ++;
} e l s e i f ( nums1 [ i ] > nums2 [ j ] ) {
j ++;
} else {
i f ( r e s u l t . isEmpty ( ) | | r e s u l t . g e t ( r e s u l t . s i z e ( ) − 1 )
!= nums1 [ i ] ) {
r e s u l t . add ( nums1 [ i ] ) ;
}
i ++;
j ++;
}
}
i n t [ ] i n t e r s e c t i o n = new i n t [ r e s u l t . s i z e ( ) ] ;
f o r ( i n t k = 0 ; k < r e s u l t . s i z e ( ) ; k++) {
i n t e r s e c t i o n [ k ] = r e s u l t . get (k) ;
}

””
 32. Intersection of Two Sorted Arrays

Problem Description
The intersection of two sorted arrays can be found using a two-pointer technique. Given two sorted arrays, nums1
and nums2, return the intersection of the two arrays. The output should be a new sorted array containing the
common elements. The input arrays are sorted in ascending order, and the output array should also be sorted in
ascending order. The algorithm should handle duplicate elements and return the common elements with the same
frequency as in the input arrays.

Example
The input arrays are: nums1 = [1, 2, 2, 3, 4, 5] nums2 = [2, 2, 4, 6, 8] The expected output is: [2, 2, 4]

Solution
i n t [ ] nums1 = { 1 , 2 , 2 , 3 , 4 , 5 } ;
i n t [ ] nums2 = { 2 , 2 , 4 , 6 , 8 } ;
int i = 0 , j = 0;
L i s t <I n t e g e r > r e s u l t = new A r r a y L i s t <>() ;
w h i l e ( i < nums1 . l e n g t h && j < nums2 . l e n g t h ) {
i f ( nums1 [ i ] < nums2 [ j ] ) {
i ++;
} e l s e i f ( nums1 [ i ] > nums2 [ j ] ) {
j ++;
} else {
r e s u l t . add ( nums1 [ i ] ) ;
i ++;
j ++;
// h a n d l e d u p l i c a t e s
w h i l e ( i < nums1 . l e n g t h && nums1 [ i ] == nums1 [ i − 1 ] ) {
r e s u l t . add ( nums1 [ i ] ) ;
i ++;
}
w h i l e ( j < nums2 . l e n g t h && nums2 [ j ] == nums2 [ j − 1 ] ) {
j ++;
}
}
}
i n t [ ] i n t e r s e c t i o n = new i n t [ r e s u l t . s i z e ( ) ] ;
f o r ( i n t k = 0 ; k < r e s u l t . s i z e ( ) ; k++) {
i n t e r s e c t i o n [ k ] = r e s u l t . get (k) ;
}

””
 33. Common Elements in Three Sorted
Arrays

Problem Description
This algorithm finds the common elements in three sorted arrays. The input consists of three sorted arrays, and the
output is a list of common elements. The algorithm assumes that the input arrays are sorted in ascending order.
The time complexity of this algorithm is O(n + m + p), where n, m, and p are the lengths of the input arrays.

Example
The input arrays are [1, 5, 10, 20, 40, 80], [6, 7, 20, 80, 100], and [3, 4, 15, 20, 30, 70, 80, 120]. The expected output
is [20, 80].

Solution
int i = 0 , j = 0 , k = 0;
i n t [ ] arr1 = {1 , 5 , 10 , 20 , 40 , 80};
i n t [ ] arr2 = {6 , 7 , 20 , 80 , 100};
i n t [ ] arr3 = {3 , 4 , 15 , 20 , 30 , 70 , 80 , 120};
w h i l e ( i < a r r 1 . l e n g t h && j < a r r 2 . l e n g t h && k < a r r 3 . l e n g t h ) {
i f ( a r r 1 [ i ] == a r r 2 [ j ] && a r r 2 [ j ] == a r r 3 [ k ] ) {
System . out . p r i n t ( a r r 1 [ i ] + ” ” ” ” ) ;
i ++;
j ++;
k++;
} e l s e i f ( a r r 1 [ i ] <= a r r 2 [ j ] && a r r 1 [ i ] <= a r r 3 [ k ] ) {
i ++;
} e l s e i f ( a r r 2 [ j ] <= a r r 1 [ i ] && a r r 2 [ j ] <= a r r 3 [ k ] ) {
j ++;
} else {
k++;
}
}

””
 34. Minimum Difference Between Elements

Problem Description
The problem requires finding the minimum difference between any two elements in a given array of integers. The
input is an array of integers and the output is the minimum difference between any two elements. The array can
contain duplicate elements and can be unsorted.

Example
For the input array [5, 3, 1, 2, 4], the expected output is 1, because the minimum difference between any two
elements is 1 (between 1 and 2 or 2 and 3 or 3 and 4).

Solution
i n t [ ] a r r = new i n t [ ] { 5 , 3 , 1 , 2 , 4 } ;
int n = arr . length ;
i n t m i n D i f f = I n t e g e r .MAX VALUE;

Arrays . s o r t ( a r r ) ;
f o r ( i n t i = 0 ; i < n − 1 ; i ++) {
int d i f f = arr [ i + 1] − arr [ i ] ;
m i n D i f f = Math . min ( minDiff , d i f f ) ;
}
System . out . p r i n t l n ( m i n D i f f ) ;

””
 35. Prefix Sum Array Construction

Problem Description
The prefix sum array construction algorithm is used to calculate the cumulative sum of elements in an array. Given
an array of integers, the task is to create a new array where each element at index i represents the sum of all
elements from index 0 to i in the original array. The input is an array of integers, and the output is a new array
containing the prefix sums.

Example
For the input array [1, 2, 3, 4, 5], the expected output is [1, 3, 6, 10, 15]. This is because the prefix sum at each
index is calculated as the sum of all elements up to that index.

Solution
i n t [ ] arr = {1 , 2 , 3 , 4 , 5};
int n = arr . length ;
i n t [ ] p r e f i x = new i n t [ n ] ;
prefix [ 0 ] = arr [ 0 ] ;
f o r ( i n t i = 1 ; i < n ; i ++) {
p r e f i x [ i ] = p r e f i x [ i −1] + a r r [ i ] ;
}

””
 36. Range Sum Query using Prefix Sums

Problem Description
The range sum query problem involves finding the sum of elements in an array within a given range [l, r]. The input
is an array of integers and the range [l, r], and the output is the sum of elements in the array from index l to r. This
problem can be solved efficiently using the prefix sums approach, where prefix[i] represents the sum of all elements
from index 0 to i.

Example
Consider the input array [1, 2, 3, 4, 5] and the range [1, 3]. The expected output is 2 + 3 + 4 = 9. The prefix sum
array for the input array would be [1, 3, 6, 10, 15]. Using the prefix sums approach, the sum of elements in the
range [1, 3] can be calculated as prefix[3] - prefix[0] = 10 - 1 = 9.

Solution
i n t [ ] nums = new i n t [ ] { 1 , 2 , 3 , 4 , 5 } ;
i n t n = nums . l e n g t h ;
i n t [ ] p r e f i x = new i n t [ n + 1 ] ;
prefix [ 0 ] = 0;
f o r ( i n t i = 0 ; i < n ; i ++) {
p r e f i x [ i + 1 ] = p r e f i x [ i ] + nums [ i ] ;
}
int l e f t = 1;
int right = 3;
i n t sum = p r e f i x [ r i g h t + 1 ] − p r e f i x [ l e f t ] ;

””
 37. Find Equilibrium Index

Problem Description
The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of
elements at higher indexes. Given an array of integers, find an equilibrium index if it exists. The input is an array
of integers and the output is the equilibrium index if it exists, otherwise -1.

Example
For the input array [-7, 1, 5, 2, -4, 3, 0], the equilibrium index is 3 because the sum of elements at lower indexes
([-7, 1, 5]) is equal to the sum of elements at higher indexes ([2, -4, 3, 0]).

Solution
i n t [ ] a r r = new i n t [ ] { −7 , 1 , 5 , 2 , −4, 3 , 0 } ;
int total sum = 0;
f o r ( i n t num : a r r ) {
t o t a l s u m += num ;
}
int left sum = 0;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
int right sum = total sum − left sum − arr [ i ] ;
i f ( l e f t s u m == r i g h t s u m ) {
System . out . p r i n t l n ( i ) ;
break ;
}
l e f t s u m += a r r [ i ] ;
}
i f ( l e f t s u m != t o t a l s u m − a r r [ a r r . l e n g t h − 1 ] ) {
System . out . p r i n t l n ( −1) ;
}

””
 38. Count Inversions in Array

Problem Description
Count inversions in an array using a modified merge sort approach or nested loops. The algorithm should take an
array of integers as input and return the total number of inversions. An inversion is a pair of elements in the array
where the first element is greater than the second element. The input array can contain duplicate elements. The
output should be the total number of inversions in the array.

Example
Consider the following example array: [1, 20, 6, 4, 5]. The expected output is 5, which corresponds to the inversions
(20, 6), (20, 4), (20, 5), (6, 4), and (6, 5).

Solution
i n t count = 0 ;
i n t [ ] temp = new i n t [ a r r . l e n g t h ] ;
mergeSort ( a r r , temp , 0 , a r r . l e n g t h − 1 ) ;
r e t u r n count ;

v o i d mergeSort ( i n t [ ] a r r , i n t [ ] temp , i n t l e f t , i n t r i g h t ) {
i f ( l e f t < right ) {
i n t mid = l e f t + ( r i g h t − l e f t ) / 2 ;
mergeSort ( a r r , temp , l e f t , mid ) ;
mergeSort ( a r r , temp , mid + 1 , r i g h t ) ;
merge ( a r r , temp , l e f t , mid , r i g h t ) ;
}
}

v o i d merge ( i n t [ ] a r r , i n t [ ] temp , i n t l e f t , i n t mid , i n t r i g h t )

{
int i = l e f t ;
i n t j = mid + 1 ;
int k = l e f t ;
w h i l e ( i <= mid && j <= r i g h t ) {
i f ( a r r [ i ] <= a r r [ j ] ) {
temp [ k ] = a r r [ i ] ;
i ++;
} else {
temp [ k ] = a r r [ j ] ;
count += mid − i + 1 ;
j ++;
}
k++;
}
w h i l e ( i <= mid ) {
temp [ k ] = a r r [ i ] ;
i ++;
 k++;
}
w h i l e ( j <= r i g h t ) {
temp [ k ] = a r r [ j ] ;
j ++;
k++;
}
f o r ( i = l e f t ; i <= r i g h t ; i ++) {
a r r [ i ] = temp [ i ] ;
}
}

””
 39. Subarray with Given Sum

Problem Description
The problem requires finding a subarray within a given one-dimensional array of integers that has a sum equal to a
specified target sum. The input consists of the array and the target sum, and the output should be the starting and
ending indices of such a subarray if it exists, or an indication that no such subarray is found. The array can contain
positive, negative, and zero integers.

Example
For the input array [10, 15, -5, 15, -10, 5] and a target sum of 5, a valid subarray with the given sum could be from
index 1 to 3 (15, -5, 15) or from index 4 to 5 (-10, 5), as both subarrays sum up to the target sum of 5.

Solution
int [ ] a r r = new i n t [ ] { 1 0 , 1 5 , −5, 1 5 , −10, 5 } ;
int targetSum = 5 ;
int windowStart = 0 ;
int currentSum = 0 ;
for ( i n t windowEnd = 0 ; windowEnd < a r r . l e n g t h ; windowEnd++) {
currentSum += a r r [ windowEnd ] ;
w h i l e ( currentSum > targetSum && windowStart <= windowEnd )
{
currentSum −= a r r [ windowStart ] ;
windowStart++;
}
i f ( currentSum == targetSum ) {
System . out . p r i n t l n ( ” ” Subarray with sum ” ” + targetSum +
” ” found from i n d e x ” ” + windowStart + ” ” t o ” ” +
windowEnd ) ;
}
}
i f ( currentSum != targetSum ) {
System . out . p r i n t l n ( ” ”No s u b a r r a y with sum ” ” + targetSum +
” ” found ” ” ) ;
}

””
 40. Subarray with Sum Divisible by K

Problem Description
The problem requires finding a subarray with a sum that is divisible by a given integer K. The input is an array of
integers and an integer K. The output should be true if such a subarray exists, and false otherwise. The algorithm
should be efficient and scalable for large inputs.

Example
For the input array [4, 5, 0, -2, -3, 1] and K = 5, the output should be true because the subarray [5] has a sum that
is divisible by 5. Another example is the input array [4, 5, 0, -2, -3, 1] and K = 7, the output should be false
because no such subarray exists.

Solution
i n t [ ] nums = new i n t [ ] { 4 , 5 , 0 , −2, −3, 1 } ;
int k = 5;
b o o l e a n found = f a l s e ;
HashMap<I n t e g e r , I n t e g e r > prefixSumMap = new HashMap<>() ;
i n t prefixSum = 0 ;
prefixSumMap . put ( 0 , 1 ) ;
f o r ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {
prefixSum += nums [ i ] ;
i n t r e m a i n d e r = prefixSum % k ;
i f ( prefixSumMap . c o n t a i n s K e y ( r e m a i n d e r ) ) {
found = t r u e ;
break ;
}
prefixSumMap . put ( remainder , 1 ) ;
}
i f ( found ) {
System . out . p r i n t l n ( t r u e ) ;
} else {
System . out . p r i n t l n ( f a l s e ) ;
}

””
 41. Subarray with Zero Sum

Problem Description
The problem requires finding a subarray with a sum of zero in a given array of integers. The input is an array of
integers and the output is a boolean indicating whether such a subarray exists. The algorithm should be efficient
and scalable for large inputs.

Example
Consider the input array [15, -2, 2, -8, 1, 7, 10, 23]. A subarray with zero sum is [-2, 2] since its sum is 0. The
expected output for this input is true, indicating the existence of such a subarray.

Solution
i n t [ ] a r r = new i n t [ ] { 1 5 , −2, 2 , −8, 1 , 7 , 1 0 , 2 3 } ;
int n = arr . length ;
b o o l e a n found = f a l s e ;
f o r ( i n t i = 0 ; i < n ; i ++) {
i n t sum = 0 ;
f o r ( i n t j = i ; j < n ; j ++) {
sum += a r r [ j ] ;
i f ( sum == 0 ) {
found = t r u e ;
break ;
}
}
i f ( found ) break ;
}
i f ( ! found ) {
j a v a . u t i l . HashMap<I n t e g e r , I n t e g e r > prefixSum = new j a v a .
u t i l . HashMap<>() ;
i n t sum = 0 ;
f o r ( i n t i = 0 ; i < n ; i ++) {
sum += a r r [ i ] ;
i f ( sum == 0 | | prefixSum . c o n t a i n s K e y ( sum ) ) {
found = t r u e ;
break ;
}
prefixSum . put ( sum , i ) ;
}
}
i f ( found ) System . out . p r i n t l n ( ” ” Subarray with z e r o sum e x i s t s ” ”
);
e l s e System . out . p r i n t l n ( ” ”No s u b a r r a y with z e r o sum e x i s t s ” ” ) ;

””
 42. Count Subarrays with Sum Equal to K

Problem Description
Count the number of subarrays in a given array that have a sum equal to k. The array can contain both positive
and negative integers. The input is an array of integers and an integer k, and the output is the count of subarrays
with sum equal to k.

Example
Input array: [-1, 0, 1, 2, -1, 4], k = 3 Expected output: 2 Explanation: Subarrays with sum 3 are [-1, 0, 1, 3] (not
present, example: [1, 2]) and [1, 2]

Solution
i n t count = 0 ;
i n t sum = 0 ;
Map<I n t e g e r , I n t e g e r > prefixSumCount = new HashMap<>() ;
prefixSumCount . put ( 0 , 1 ) ;
f o r ( i n t num : nums ) {
sum += num ;
count += prefixSumCount . g e t O r D e f a u l t ( sum − k , 0 ) ;
prefixSumCount . put ( sum , prefixSumCount . g e t O r D e f a u l t ( sum , 0 )
+ 1) ;
}
r e t u r n count ;

””
 43. Maximum Sum Contiguous Subarray

Problem Description
The maximum sum contiguous subarray problem is the task of finding a contiguous subarray within a
one-dimensional array of numbers that has the largest sum. The input is a list of integers, and the output is the
maximum sum of a contiguous subarray. The algorithm should be able to handle arrays with both positive and
negative numbers.

Example
For the input array [-2, -3, 4, -1, -2, 1, 5, -3], the maximum sum contiguous subarray is [4, -1, -2, 1, 5] with a sum of
7.

Solution
int m a x s o f a r = −1000000;
int max ending here = 0 ;
int [ ] a r r = { −2 , −3, 4 , −1, −2, 1 , 5 , −3};
for ( int i = 0; i < arr . length ; i ++) {
m a x e n d i n g h e r e += a r r [ i ] ;
i f ( max so far < max ending here ) {
max so far = max ending here ;
}
i f ( max ending here < 0) {
max ending here = 0 ;
}
}
System . out . p r i n t l n ( m a x s o f a r ) ;

””
 44. Maximum Product Subarray

Problem Description
The maximum product subarray problem is a variation of the maximum subarray problem. Given an integer array,
find the maximum product of a subarray within the array. The subarray must contain at least one number. The
input is an integer array, and the output is the maximum product of a subarray. The array can contain both
positive and negative numbers.

Example
Consider the input array [-2, 3, -4]. The maximum product subarray is [-2, 3, -4] with a product of 24. Another
example is the input array [1, -2, -3, 0, 7, -8, -2]. The maximum product subarray is [-2, -3, 0, 7, -8, -2] is not the
correct answer, the correct answer would be the subarray [7] or [-2, -3, 0, 7] is not correct either, the correct
subarray would be [7] with a product of 7.

Solution
int maxProduct = I n t e g e r . MIN VALUE ;
int [ ] nums = new i n t [ ] { /∗ i n p u t a r r a y ∗/ } ;
int maxSoFar = nums [ 0 ] ;
int minSoFar = nums [ 0 ] ;
int r e s u l t = nums [ 0 ] ;
for ( i n t i = 1 ; i < nums . l e n g t h ; i ++) {
i f ( nums [ i ] < 0 ) {
i n t temp = maxSoFar ;
maxSoFar = minSoFar ;
minSoFar = temp ;
}
maxSoFar = Math . max( nums [ i ] , maxSoFar ∗ nums [ i ] ) ;
minSoFar = Math . min ( nums [ i ] , minSoFar ∗ nums [ i ] ) ;
r e s u l t = Math . max( r e s u l t , maxSoFar ) ;
}
return r e s u l t ;

””
 45. Maximum Circular Subarray Sum

Problem Description
The maximum circular subarray sum problem is a variation of the maximum subarray sum problem. Given an
array of integers, find the maximum sum of a subarray that can be obtained by considering the array as a circular
array. The input is an array of integers and the output is the maximum sum of a subarray. The array can contain
both positive and negative integers.

Example
Consider the array [5, -3, 5]. The maximum circular subarray sum is 10, which can be obtained by considering the
subarray [5, 5]. Another example is the array [1, 2, 3, -4, 5], where the maximum circular subarray sum is 8, which
can be obtained by considering the subarray [1, 2, 3, 5] in a circular manner, treating the array as [5, 1, 2, 3, -4] and
then taking the subarray [5, 1, 2].

Solution
int max kadane = I n t e g e r . MIN VALUE ;
int max ending here = 0 ;
int total sum = 0;
for ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {
m a x e n d i n g h e r e = m a x e n d i n g h e r e + nums [ i ] ;
i f ( max kadane < m a x e n d i n g h e r e ) {
max kadane = m a x e n d i n g h e r e ;
}
i f ( max ending here < 0) {
max ending here = 0 ;
}
t o t a l s u m += nums [ i ] ;
}

i n t min kadane = I n t e g e r .MAX VALUE;

int min ending here = 0;
f o r ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {
m i n e n d i n g h e r e = m i n e n d i n g h e r e + nums [ i ] ;
i f ( min kadane > m i n e n d i n g h e r e ) {
min kadane = m i n e n d i n g h e r e ;
}
i f ( min ending here > 0) {
min ending here = 0;
}
}

i f ( t o t a l s u m == min kadane ) {
r e s u l t = max kadane ;
} else {
r e s u l t = Math . max( max kadane , t o t a l s u m − min kadane ) ;
}
””
 46. Longest Increasing Subsequence Length

Problem Description
The longest increasing subsequence length problem is a classic problem in computer science and mathematics.
Given an array of integers, find the length of the longest subsequence that is strictly increasing. The subsequence
can be non-contiguous, meaning that the elements do not have to be adjacent in the original array. The input is an
array of integers, and the output is the length of the longest increasing subsequence.

Example
For example, given the input array [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101], and
the output is 4. Another example is the input array [0, 1, 0, 3, 2, 3], where the longest increasing subsequence is [0,
1, 3], and the output is 3.

Solution
int [ ] nums = new i n t [ ] { 1 0 , 9 , 2 , 5 , 3 , 7 , 1 0 1 , 1 8 } ;
int n = nums . l e n g t h ;
int [ ] dp = new i n t [ n ] ;
for ( i n t i = 0 ; i < n ; i ++) {
dp [ i ] = 1 ;
}
f o r ( i n t i = 1 ; i < n ; i ++) {
f o r ( i n t j = 0 ; j < i ; j ++) {
i f ( nums [ i ] > nums [ j ] ) {
dp [ i ] = Math . max( dp [ i ] , dp [ j ] + 1 ) ;
}
}
}
i n t max = dp [ 0 ] ;
f o r ( i n t i = 1 ; i < n ; i ++) {
max = Math . max(max , dp [ i ] ) ;
}
System . out . p r i n t l n (max) ;

””
 47. Longest Bitonic Subsequence

Problem Description
The longest bitonic subsequence problem is a variation of the longest increasing subsequence problem. A bitonic
subsequence is a sequence that first increases and then decreases. The problem requires finding the length of the
longest bitonic subsequence in a given array of integers. The input is an array of integers and the output is the
length of the longest bitonic subsequence.

Example
For the input array [1, 2, 3, 4, 5, 4, 3, 2, 1], the longest bitonic subsequence is [1, 2, 3, 4, 5, 4, 3, 2, 1] with a length
of 9. For the input array [1, 15, 51, 45, 33, 100, 12, 18, 9], the longest bitonic subsequence is [1, 15, 51, 45, 33, 100]
or [1, 15, 51, 45, 33, 9] with a length of 6.

Solution
int [] a r r = new i n t [ ] { 1 , 1 5 , 5 1 , 4 5 , 3 3 , 1 0 0 , 1 2 , 1 8 , 9 } ;
int n = arr . length ;
int [] l i s L e f t = new i n t [ n ] ;
int [] l i s R i g h t = new i n t [ n ] ;

f o r ( i n t i = 0 ; i < n ; i ++) {
l i s L e f t [ i ] = 1;
lisRight [ i ] = 1;
}

f o r ( i n t i = 1 ; i < n ; i ++) {
f o r ( i n t j = 0 ; j < i ; j ++) {
i f ( a r r [ i ] > a r r [ j ] && l i s L e f t [ i ] < l i s L e f t [ j ] + 1 ) {
l i s L e f t [ i ] = l i s L e f t [ j ] + 1;
}
}
}

f o r ( i n t i = n − 2 ; i >= 0 ; i −−) {
f o r ( i n t j = n − 1 ; j > i ; j −−) {
i f ( a r r [ i ] > a r r [ j ] && l i s R i g h t [ i ] < l i s R i g h t [ j ] + 1 ) {
lisRight [ i ] = lisRight [ j ] + 1;
}
}
}

i n t maxLen = 0 ;
f o r ( i n t i = 0 ; i < n ; i ++) {
maxLen = Math . max( maxLen , l i s L e f t [ i ] + l i s R i g h t [ i ] − 1 ) ;
}

System . out . p r i n t l n ( maxLen ) ;

””
 48. Sliding Window Maximum

Problem Description
The sliding window maximum problem involves finding the maximum value in each window of a given size that
slides over an array of integers. The input is an array of integers and a window size. The output is an array of
maximum values, where each maximum value corresponds to the maximum element in the window of the given size.
The window slides from left to right, and for each position, the maximum element in the current window is added to
the output array.

Example
For the input array [1, 3, -1, -3, 5, 3, 6, 7] and a window size of 3, the output array would be [3, 3, 5, 5, 6, 7]. This
is because the maximum elements in each window of size 3 are 3 (for the window [1, 3, -1]), 3 (for the window [3, -1,
-3]), 5 (for the window [-1, -3, 5]), 5 (for the window [-3, 5, 3]), 6 (for the window [5, 3, 6]), and 7 (for the window
[3, 6, 7]).

Solution
i n t [ ] maxSlidingWindow ( i n t [ ] nums , i n t k ) {
i n t [ ] output = new i n t [ nums . l e n g t h − k + 1 ] ;
j a v a . u t i l . Deque<I n t e g e r > deque = new j a v a . u t i l . L i n k e d L i s t
<>() ;

f o r ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {

w h i l e ( ! deque . isEmpty ( ) && deque . p e e k F i r s t ( ) < i − k +
1) {
deque . p o l l F i r s t ( ) ;
}
w h i l e ( ! deque . isEmpty ( ) && nums [ deque . p e e k L a s t ( ) ] <
nums [ i ] ) {
deque . p o l l L a s t ( ) ;
}
deque . o f f e r L a s t ( i ) ;
i f ( i >= k − 1 ) {
output [ i − k + 1 ] = nums [ deque . p e e k F i r s t ( ) ] ;
}
}
r e t u r n output ;
}

””
49. Count Distinct Elements in Each Window
of Size K

Problem Description
Count distinct elements in each window of size k in an array of integers. The input is an array of integers and an
integer k, representing the window size. The output should be an array of integers, where each integer represents
the number of distinct elements in the corresponding window.

Example
For the input array [1, 2, 2, 3, 4, 4, 5] and k = 3, the output should be [2, 3, 3, 3, 3]. The windows are [1, 2, 2], [2,
2, 3], [2, 3, 4], [3, 4, 4], [4, 4, 5], and the number of distinct elements in each window is 2, 2, 3, 3, 2 respectively, but
since we are considering the window size as 3, the first window [1,2,2] has 2 distinct elements, the second window
[2,2,3] has 2 distinct elements, the third window [2,3,4] has 3 distinct elements, the fourth window [3,4,4] has 2
distinct elements, and the fifth window [4,4,5] has 2 distinct elements. However, the correct interpretation is that
we should be counting distinct elements in each window of size k, so the correct output should be [2, 3, 3, 3, 3] is
incorrect and the correct output is [2, 2, 3, 2, 2].

Solution
i n t [ ] c o u n t D i s t i n c t ( i n t [ ] nums , i n t k ) {
i n t n = nums . l e n g t h ;
i n t [ ] r e s u l t = new i n t [ n − k + 1 ] ;
f o r ( i n t i = 0 ; i <= n − k ; i ++) {
j a v a . u t i l . HashMap<I n t e g e r , I n t e g e r > map = new j a v a . u t i l
. HashMap<>() ;
f o r ( i n t j = i ; j < i + k ; j ++) {
map . put ( nums [ j ] , map . g e t O r D e f a u l t ( nums [ j ] , 0 ) + 1 ) ;
}
r e s u l t [ i ] = map . s i z e ( ) ;
}
return r e s u l t ;
}

””
 50. Smallest Subarray with Sum Target

Problem Description
The problem requires finding the smallest subarray within a given array that has a sum greater than or equal to a
specified target value. The input consists of an array of integers and a target sum. The output should be the length
of the smallest subarray that meets the condition. If no such subarray exists, the output should indicate this.

Example
For the input array [2, 3, 1, 2, 4, 3] and a target sum of 7, the smallest subarray with a sum greater than or equal to
the target is [4, 3], which has a length of 2.

Solution
int l e f t = 0;
int m i n l e n g t h = I n t e g e r .MAX VALUE;
int current sum = 0 ;
for ( i n t r i g h t = 0 ; r i g h t < a r r a y . l e n g t h ; r i g h t ++) {
c u r r e n t s u m += a r r a y [ r i g h t ] ;
w h i l e ( c u r r e n t s u m >= t a r g e t ) {
m i n l e n g t h = Math . min ( m i n l e n g t h , r i g h t − l e f t + 1 ) ;
c u r r e n t s u m −= a r r a y [ l e f t ] ;
l e f t ++;
}
}
i f ( m i n l e n g t h == I n t e g e r .MAX VALUE) {
r e t u r n −1; // or any o t h e r v a l u e t o i n d i c a t e no such
subarray e x i s t s
} else {
return min length ;
}

””
 51. Smallest Subarray to Sort Entire Array

Problem Description
The problem requires finding the smallest subarray that needs to be sorted in order to sort the entire array. The
input is an array of integers and the output is the start and end indices of the smallest subarray. The algorithm
should have a time complexity of O(n) where n is the number of elements in the array.

Example
For the input array [3, 7, 5, 6, 9], the output should be [1, 3] because the subarray [7, 5, 6] needs to be sorted to sort
the entire array. For the input array [1, 2, 3, 4, 5], the output should be [-1, -1] because the array is already sorted.

Solution
int n = nums . l e n g t h ;
int s t a r t = −1, end = −1;
int maxSoFar = I n t e g e r . MIN VALUE, minSoFar = I n t e g e r .MAX VALUE;
for ( i n t i = 0 ; i < n ; i ++) {
i f ( s t a r t == −1 && nums [ i ] > minSoFar ) {
start = i − 1;
}
i f ( s t a r t != −1 && nums [ i ] < maxSoFar ) {
end = i + 1 ;
}
i f ( nums [ i ] < minSoFar ) {
minSoFar = nums [ i ] ;
}
i f ( nums [ i ] > maxSoFar ) {
maxSoFar = nums [ i ] ;
}
}
i f ( s t a r t == −1) {
System . out . p r i n t l n ( ” ” [ −1 , −1] ” ” ) ;
} else {
System . out . p r i n t l n ( ” ” [ ” ” + s t a r t + ” ” , ” ” + end + ” ” ] ” ” ) ;
}

””
 52. Largest Subarray with Equal 0s and 1s

Problem Description
The problem requires finding the largest subarray with an equal number of 0s and 1s in a given binary array. The
input is a binary array, and the output should be the length of the largest subarray with equal 0s and 1s. The
approach involves converting all 0s to -1 and then finding the longest subarray with a sum of 0.

Example
Consider the binary array [1, 0, 1, 0, 1, 0, 1]. The expected output is 8, as the entire array has an equal number of
0s and 1s. Another example is [1, 1, 0, 0, 1, 0], where the expected output is 4, corresponding to the subarray [1, 1,
0, 0].

Solution
i n t maxLen = 0 ;
i n t [ ] a r r = new i n t [ ] { 1 , 0 , 1 , 0 , 1 , 0 , 1 } ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
i f ( a r r [ i ] == 0 ) {
a r r [ i ] = −1;
}
}
i n t sum = 0 ;
HashMap<I n t e g e r , I n t e g e r > map = new HashMap<>() ;
map . put ( 0 , −1) ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
sum += a r r [ i ] ;
i f (map . c o n t a i n s K e y ( sum ) ) {
maxLen = Math . max( maxLen , i − map . g e t ( sum ) ) ;
} else {
map . put ( sum , i ) ;
}
}

””
 53. Trapping Rain Water

Problem Description
The trapping rain water problem is a classic problem in algorithm design. Given an array of non-negative integers
representing the height of bars in a histogram, find the amount of water that can be trapped between the bars. The
input is an array of integers, and the output is the total amount of water that can be trapped. The bars are
represented as lines in a histogram, and the water is trapped between the bars.

Example
For example, given the input [0,1,0,2,1,0,1,3,2,1,2,1], the output is 6. The water is trapped between the bars as
follows: the area between the first and second bar (1 unit), the area between the second and third bar (1 unit), the
area between the fourth and fifth bar (1 unit), the area between the sixth and seventh bar (1 unit), the area
between the seventh and eighth bar (2 units), and the area between the ninth and tenth bar (1 unit), and the area
between the tenth and eleventh bar (1 unit) and the area between the eleventh and twelfth bar (1 unit) but only 6
units are trapped.

Solution
int trap = 0;
int l e f t = 0;
int right = height . length − 1;
i n t maxLeft = 0 ;
i n t maxRight = 0 ;
w h i l e ( l e f t <= r i g h t ) {
i f ( height [ l e f t ] < height [ right ] ) {
i f ( h e i g h t [ l e f t ] >= maxLeft ) {
maxLeft = h e i g h t [ l e f t ] ;
} else {
t r a p += maxLeft − h e i g h t [ l e f t ] ;
}
l e f t ++;
} else {
i f ( h e i g h t [ r i g h t ] >= maxRight ) {
maxRight = h e i g h t [ r i g h t ] ;
} else {
t r a p += maxRight − h e i g h t [ r i g h t ] ;
}
r i g h t −−;
}
}
return trap ;

””
 54. Stock Buy Sell Maximum Profit

Problem Description
The stock buy sell maximum profit problem is a classic problem in algorithm design. The goal is to find the
maximum possible profit from a single transaction (buy and sell) given a list of stock prices for each day. The input
is a list of integers representing the stock prices, and the output is the maximum possible profit. The algorithm
should be efficient and scalable.

Example
For example, given the input [7, 1, 5, 3, 6, 4], the output should be 5, because the maximum profit can be achieved
by buying at price 1 and selling at price 6.

Solution
i n t ma xPr of it = 0 ;
i n t minPriceSoFar = I n t e g e r .MAX VALUE;
for ( int price : prices ) {
minPriceSoFar = Math . min ( minPriceSoFar , p r i c e ) ;
i n t p o t e n t i a l P r o f i t = p r i c e − minPriceSoFar ;
ma xP ro fit = Math . max( maxProfit , p o t e n t i a l P r o f i t ) ;
}
r e t u r n ma xP ro fit ;

””
 55. Stock Buy Sell Maximum Profit

Problem Description
The stock buy sell maximum profit problem is a classic problem in algorithm design. The goal is to find the
maximum possible profit from a series of stock transactions, where you can buy and sell stocks multiple times. The
input is an array of integers representing the stock prices on different days. The output is the maximum possible
profit that can be achieved. The problem can be solved using a peak-valley approach or dynamic programming.

Example
For example, given the input array [7, 1, 5, 3, 6, 4], the maximum possible profit is 7, which can be achieved by
buying on day 2 (price 1) and selling on day 3 (price 5), then buying on day 4 (price 3) and selling on day 5 (price
6). The expected output is 7.

Solution
i n t ma xP rof it = 0 ;
i n t [ ] p r i c e s = new i n t [ ] { 7 , 1 , 5 , 3 , 6 , 4 } ;
f o r ( i n t i = 1 ; i < p r i c e s . l e n g t h ; i ++) {
i f ( prices [ i ] > prices [ i − 1]) {
m axP ro fi t += p r i c e s [ i ] − p r i c e s [ i − 1 ] ;
}
}
System . out . p r i n t l n ( m axP ro fi t ) ;

””
 56. Gas Station Tour

Problem Description
The gas station tour problem is a classic problem where we have a circular tour of gas stations, and we need to find
the starting point for the tour such that we never run out of fuel. We are given two arrays, one representing the
amount of fuel available at each station and the other representing the amount of fuel consumed to reach the next
station. The goal is to determine if it’s possible to complete the tour and find the starting point.
Input: - Fuel array (fuel available at each station) - Consumption array (fuel consumed to reach the next station)
Output: - Starting point for the tour (if possible) - -1 if it’s not possible to complete the tour

Example
Sample input: Fuel array: [1, 2, 3, 4, 5] Consumption array: [3, 4, 5, 1, 2] Expected output: Starting point: 3

Solution
int totalFuel = 0;
int totalConsumption = 0 ;
int start = 0;
int tank = 0 ;

f o r ( i n t i = 0 ; i < f u e l . l e n g t h ; i ++) {
t o t a l F u e l += f u e l [ i ] ;
t o t a l C o n s u m p t i o n += consumption [ i ] ;
tank += f u e l [ i ] − consumption [ i ] ;
i f ( tank < 0 ) {
start = i + 1;
tank = 0 ;
}
}

i f ( t o t a l F u e l < totalConsumption ) {
System . out . p r i n t l n ( −1) ;
} else {
System . out . p r i n t l n ( s t a r t ) ;
}

””
 57. Minimum Jumps to Reach End

Problem Description
The problem requires finding the minimum number of jumps to reach the end of an array, where each element
represents the maximum jump length from that position. The input is an array of integers, and the output is the
minimum number of jumps to reach the end. The array is 0-indexed, and the first element is always reachable.

Example
For the input array [2, 3, 1, 1, 4], the expected output is 2, because the minimum number of jumps to reach the end
is 2 (0 -¿ 1 -¿ 4). For the input array [2, 3, 0, 1, 4], the expected output is 2, because the minimum number of
jumps to reach the end is 2 (0 -¿ 1 -¿ 4).

Solution
int jumps = 0 ;
int currEnd = 0 ;
int farthest = 0;
for ( i n t i = 0 ; i < a r r . l e n g t h − 1 ; i ++) {
f a r t h e s t = Math . max( f a r t h e s t , i + a r r [ i ] ) ;
i f ( i == currEnd ) {
jumps++;
currEnd = f a r t h e s t ;
}
}

””
 58. Minimum Swaps to Sort Array

Problem Description
The problem requires finding the minimum number of swaps to sort an array. The array is 0-indexed and contains
distinct elements from 0 to n-1. The input is an array of integers, and the output is the minimum number of swaps
required to sort the array.

Example
For the input array [4, 3, 1, 2, 0], the expected output is 4 because we need at least 4 swaps to sort the array: (4,
0), (3, 1), (4, 2), (3, 1).

Solution
int n = arr . length ;
b o o l e a n [ ] v i s i t e d = new b o o l e a n [ n ] ;
i n t ans = 0 ;

f o r ( i n t i = 0 ; i < n ; i ++) {
if (! visited [ i ]) {
int cycle size = 0;
int j = i ;
while ( ! v i s i t e d [ j ] ) {
v i s i t e d [ j ] = true ;
j = arr [ j ] ;
c y c l e s i z e ++;
}
i f ( c y c l e s i z e > 0) {
ans += ( c y c l e s i z e − 1 ) ;
}
}
}
r e t u r n ans ;

””
59. Largest Sum with No Adjacent Elements

Problem Description
The problem requires finding the largest sum that can be obtained from a list of numbers without selecting any two
adjacent elements. The input is a list of integers, and the output is the maximum sum that can be achieved. The
algorithm should be efficient and scalable for large inputs.

Example
For the input list [5, 1, 1, 5], the expected output is 10, which can be achieved by selecting the first and last
elements (5 + 5). For the input list [2, 4, 6, 2, 5], the expected output is 13, which can be achieved by selecting the
elements at indices 0, 2, and 4 (2 + 6 + 5).

Solution
i n t prev2 = 0 ;
i n t prev1 = 0 ;
f o r ( i n t num : nums ) {
i n t temp = prev1 ;
prev1 = Math . max( prev2 + num , prev1 ) ;
prev2 = temp ;
}
r e t u r n prev1 ;

””
 60. Maximum Difference Between Two
Elements

Problem Description
The goal is to find the maximum difference between two elements in an array, with the constraint that the smaller
element must appear before the larger one. The input is an array of integers, and the output is the maximum
difference that satisfies the condition. The array can contain duplicate elements and may be empty.

Example
Consider the input array [2, 3, 10, 6, 4, 8, 1], the maximum difference is 8 (10 - 2). For the array [7, 1, 5, 4], the
maximum difference is 4 (5 - 1).

Solution
i n t minSoFar = I n t e g e r .MAX VALUE;
i n t maxDiff = 0 ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
i f ( a r r [ i ] < minSoFar ) {
minSoFar = a r r [ i ] ;
} e l s e i f ( a r r [ i ] − minSoFar > maxDiff ) {
maxDiff = a r r [ i ] − minSoFar ;
}
}
r e t u r n maxDiff ;

””
 61. Palindrome Check

Problem Description
The goal is to determine whether a given string is a palindrome. A palindrome is a string that reads the same
backward as forward. The algorithm should take a string as input and return a boolean value indicating whether
the string is a palindrome or not. The input string may contain spaces, punctuation, or special characters, but these
should be ignored when checking for palindromes. The algorithm should be case-insensitive.

Example
Input: ””A man, a plan, a canal: Panama”” Output: true Input: ””Not a palindrome”” Output: false

Solution
left = 0
right = s . length − 1
while l e f t < right
i f s . charAt ( l e f t ) == ’ ’
l e f t += 1
e l s e i f s . charAt ( r i g h t ) == ’ ’
r i g h t −= 1
e l s e i f C h a r a c t e r . toLowerCase ( s . charAt ( l e f t ) ) !=
C h a r a c t e r . toLowerCase ( s . charAt ( r i g h t ) )
return f a l s e
else
l e f t += 1
r i g h t −= 1
return true

””
 62. Reverse String

Problem Description
The goal of this algorithm is to reverse a given string. The input is a string of characters, and the output should be
the reversed string. For example, if the input is ””hello””, the output should be ””olleh””. The algorithm should
handle strings of any length and containing any characters.

Example
Input: ””hello”” Output: ””olleh”” Input: ””abcde”” Output: ””edcba””

Solution
S t r i n g s t r = ”” h e l l o ”” ;
c h a r [ ] a r r = s t r . toCharArray ( ) ;
int l e f t = 0;
int right = arr . length − 1;
while ( l e f t < right ) {
c h a r temp = a r r [ l e f t ] ;
arr [ l e f t ] = arr [ right ] ;
a r r [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}
S t r i n g r e v e r s e d S t r = new S t r i n g ( a r r ) ;

””
 63. Reverse Words in a Sentence

Problem Description
The goal of this algorithm is to reverse the order of words in a given sentence. The input is a string of words
separated by spaces, and the output should be a string with the words in reverse order. For example, the input
””Hello World”” should result in the output ””World Hello””. The algorithm should handle sentences with multiple
words and preserve the original spacing between words.

Example
The input sentence ””This is a test”” should be reversed to ””test a is This””. The algorithm should work with any
number of words in the sentence.

Solution
S t r i n g [ ] words = s e n t e n c e . s p l i t ( ” ” ” ” ) ;
int l e f t = 0;
i n t r i g h t = words . l e n g t h − 1 ;
while ( l e f t < right ) {
S t r i n g temp = words [ l e f t ] ;
words [ l e f t ] = words [ r i g h t ] ;
words [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}
S t r i n g r e v e r s e d S e n t e n c e = S t r i n g . j o i n ( ” ” ” ” , words ) ;

””
 64. Reverse Vowels

Problem Description
Reverse only the vowels in a given string, keeping the consonants and other characters in their original positions.
The input is a string containing a mix of vowels and consonants, and the output should be the modified string with
only the vowels reversed.

Example
Given the string ””hello””, the expected output would be ””holle””. For the string ””aeiou””, the output should be
””uoiea””.

Solution
c h a r [ ] c h a r s = s . toCharArray ( ) ;
int l e f t = 0;
int right = s . length () − 1;
while ( l e f t < right ) {
i f ( ! isVowel ( chars [ l e f t ] ) ) {
l e f t ++;
} e l s e i f ( ! isVowel ( chars [ r i g h t ] ) ) {
r i g h t −−;
} else {
c h a r temp = c h a r s [ l e f t ] ;
chars [ l e f t ] = chars [ right ] ;
c h a r s [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}
}
S t r i n g r e s u l t = new S t r i n g ( c h a r s ) ;

””
 65. Vowel and Consonant Counter

Problem Description
This algorithm takes a string as input and returns the count of vowels and consonants in the string. The input is a
single string, and the output is the count of vowels and consonants. The algorithm iterates over the string, checks
each character, and increments the corresponding count.

Example
Input: ””hello world”” Output: Vowels: 3, Consonants: 7

Solution
i n t vowels = 0 ;
i n t consonants = 0;
S t r i n g s t r = ” ” h e l l o world ” ” ;
f o r ( i n t i = 0 ; i < s t r . l e n g t h ( ) ; i ++) {
c h a r c = s t r . charAt ( i ) ;
i f ( c == ’ a ’ | | c == ’ e ’ | | c == ’ i ’ | | c == ’ o ’ | | c == ’ u
’ ||
c == ’A ’ | | c == ’E ’ | | c == ’ I ’ | | c == ’O ’ | | c == ’U
’) {
v o w e l s++;
} e l s e i f ( c >= ’ a ’ && c <= ’ z ’ | | c >= ’A ’ && c <= ’ Z ’ ) {
c o n s o n a n t s ++;
}
}
System . out . p r i n t l n ( ” ” Vowels : ” ” + v o w e l s + ” ” , Consonants : ” ” +
consonants ) ;

””
 66. Remove Spaces from String

Problem Description
The problem requires removing all spaces from a given string. The input is a string that may contain multiple
spaces, and the output should be the same string without any spaces. The algorithm should be efficient and
scalable for large input strings.

Example
Input: ””Hello World”” Output: ””HelloWorld”” The example shows a simple string with one space. The algorithm
should be able to handle strings with multiple spaces, leading spaces, trailing spaces, and consecutive spaces.

Solution
S t r i n g r e s u l t = ”””” ;
f o r ( i n t i = 0 ; i < s . l e n g t h ( ) ; i ++) {
i f ( s . charAt ( i ) != ’ ’ ) {
r e s u l t += s . charAt ( i ) ;
}
}
return r e s u l t ;

””
 67. Remove Extra Spaces

Problem Description
The algorithm removes extra spaces from a given string, leaving only one space between words. Input: A string
containing multiple spaces between words. Output: A string with single spaces between words.

Example
Input string: ””Hello World this is a test”” Expected output: ””Hello World this is a test””

Solution
int i = 0;
int j = 0;
char [ ] s t r = ”” Hello World t h i s is a t e s t ” ” . toCharArray
() ;
while ( j < s t r . length ) {
i f ( s t r [ j ] != ’ ’ | | ( i != 0 && s t r [ i − 1 ] != ’ ’ ) ) {
s t r [ i ++] = s t r [ j ] ;
}
j ++;
}
S t r i n g r e s u l t = new S t r i n g ( s t r , 0 , i ) ;

””
 68. Case Conversion

Problem Description
The case conversion algorithm takes a string as input and converts it to either uppercase or lowercase. The input
string can contain a mix of uppercase and lowercase letters, as well as other characters. The algorithm should
output the converted string. The input and output specifications are as follows: input: a string output: the input
string converted to either uppercase or lowercase

Example
The input string ””HeLlO”” can be converted to either ””HELLO”” (uppercase) or ””hello”” (lowercase). Another
example is the string ””WoRlD””, which can be converted to ””WORLD”” (uppercase) or ””world”” (lowercase).

Solution
c h a r [ ] s t r = new c h a r [ ] { ’H ’ , ’ e ’ , ’L ’ , ’ l ’ , ’O ’ } ;
b o o l e a n toUpper = t r u e ;
f o r ( i n t i = 0 ; i < s t r . l e n g t h ; i ++) {
i f ( C h a r a c t e r . isLowerCase ( s t r [ i ] ) && toUpper ) {
s t r [ i ] = C h a r a c t e r . toUpperCase ( s t r [ i ] ) ;
} e l s e i f ( C h a r a c t e r . isUpperCase ( s t r [ i ] ) && ! toUpper ) {
s t r [ i ] = C h a r a c t e r . toLowerCase ( s t r [ i ] ) ;
}
}
System . out . p r i n t l n ( new S t r i n g ( s t r ) ) ;

””
 69. String Contains Only Digits

Problem Description
The task is to determine whether a given string consists entirely of digits. The input is a string, and the output
should be a boolean value indicating whether all characters in the string are digits. The algorithm should handle
strings of varying lengths and containing different characters.

Example
Input: ””12345”” Output: true Input: ””123abc”” Output: false

Solution
boolean containsOnlyDigits = true ;
S t r i n g i n p u t = ” ” 12345 ” ” ;
f o r ( c h a r c : i n p u t . toCharArray ( ) ) {
i f ( ! Character . i s D i g i t ( c ) ) {
containsOnlyDigits = f a l s e ;
break ;
}
}
System . out . p r i n t l n ( c o n t a i n s O n l y D i g i t s ) ;

””
 70. String Length Calculation

Problem Description
The goal is to calculate the length of a given string without using the built-in strlen function. The input is a string,
and the output should be the length of this string. The approach involves looping through the string until a null
character is encountered, incrementing a counter for each character.

Example
For the input string ””example””, the expected output is 7, since there are 7 characters in the string. The input can
be any string, and the output will be the number of characters in that string.

Solution
c h a r [ ] s t r = ” ” example ” ” ;
int length = 0;
f o r ( i n t i = 0 ; s t r [ i ] != ’ \0 ’ ; i ++) {
l e n g t h ++;
}
System . out . p r i n t l n ( l e n g t h ) ;

””
 71. Anagram Checker

Problem Description
Check if two input strings are anagrams of each other. An anagram is a word or phrase formed by rearranging the
letters of a different word or phrase, typically using all the original letters exactly once. The input consists of two
strings, and the output should be a boolean value indicating whether the strings are anagrams. The algorithm
should be case-sensitive and consider spaces and punctuation as characters.

Example
Input: str1 = ””listen””, str2 = ””silent”” Output: true Input: str1 = ””hello””, str2 = ””world”” Output: false

Solution
c h a r [ ] s t r 1 = new c h a r [ 1 0 0 ] ;
c h a r [ ] s t r 2 = new c h a r [ 1 0 0 ] ;
b o o l e a n areAnagrams = f a l s e ;
i n t [ ] f r e q 1 = new i n t [ 2 5 6 ] ;
i n t [ ] f r e q 2 = new i n t [ 2 5 6 ] ;

// I n i t i a l i z e f r e q u e n c y a r r a y s
f o r ( i n t i = 0 ; i < 2 5 6 ; i ++) {
freq1 [ i ] = 0;
freq2 [ i ] = 0;
}

// Read i n p u t s t r i n g s
s t r 1 = ” ” l i s t e n ” ” . toCharArray ( ) ;
s t r 2 = ” ” s i l e n t ” ” . toCharArray ( ) ;

// C a l c u l a t e f r e q u e n c y o f c h a r a c t e r s i n b o t h s t r i n g s
f o r ( i n t i = 0 ; i < s t r 1 . l e n g t h ; i ++) {
f r e q 1 [ s t r 1 [ i ]]++;
}
f o r ( i n t i = 0 ; i < s t r 2 . l e n g t h ; i ++) {
f r e q 2 [ s t r 2 [ i ]]++;
}

// Compare f r e q u e n c y a r r a y s
i f ( s t r 1 . l e n g t h == s t r 2 . l e n g t h ) {
areAnagrams = t r u e ;
f o r ( i n t i = 0 ; i < 2 5 6 ; i ++) {
i f ( f r e q 1 [ i ] != f r e q 2 [ i ] ) {
areAnagrams = f a l s e ;
break ;
}
}
}
// P r i n t r e s u l t
i f ( areAnagrams ) {
System . out . p r i n t l n ( ” ” t r u e ” ” ) ;
} else {
System . out . p r i n t l n ( ” ” f a l s e ” ” ) ;
}

””
 72. Group Anagrams

Problem Description
The goal is to group a list of strings into anagrams. An anagram is a word or phrase formed by rearranging the
letters of a different word or phrase, typically using all the original letters exactly once. The input is a list of
strings, and the output should be a list of lists where each sublist contains strings that are anagrams of each other.

Example
Input: strs = [””eat””, ””tea””, ””tan””, ””ate””, ””nat””, ””bat””] Output:
[[””eat””,””tea””,””ate””],[””tan””,””nat””],[””bat””]]

Solution
Map<S t r i n g , L i s t <S t r i n g >> anagrams = new HashMap<>() ;
f o r ( S t r i n g word : s t r s ) {
c h a r [ ] c h a r s = word . toCharArray ( ) ;
Arrays . s o r t ( c h a r s ) ;
S t r i n g sortedWord = new S t r i n g ( c h a r s ) ;
i f ( ! anagrams . c o n t a i n s K e y ( sortedWord ) ) {
anagrams . put ( sortedWord , new A r r a y L i s t <>() ) ;
}
anagrams . g e t ( sortedWord ) . add ( word ) ;
}
L i s t <L i s t <S t r i n g >> r e s u l t = new A r r a y L i s t <>(anagrams . v a l u e s ( ) ) ;

””
 73. Find First Non-Repeating Character

Problem Description
Find the first non-repeating character in a given string. The input is a string of characters, and the output should be
the first character that appears only once in the string. If no such character exists, the output should indicate that.

Example
Input: ””aabbc”” Output: ””c”” Explanation: ’c’ is the first character that appears only once in the string.

Solution
c h a r [ ] s = new c h a r [ ] { ’ a ’ , ’ a ’ , ’ b ’ , ’ b ’ , ’ c ’ } ;
i n t [ ] f r e q = new i n t [ 2 5 6 ] ;
f o r ( char c : s ) {
f r e q [ c ] += 1 ;
}
f o r ( char c : s ) {
i f ( f r e q [ c ] == 1 ) {
System . out . p r i n t l n ( c ) ;
break ;
}
}

””
 74. First Repeating Character

Problem Description
The first repeating character algorithm finds the first character that repeats in a given string. The input is a string
of characters, and the output is the first repeating character. If no character repeats, the output is a null or empty
value. The algorithm should have a time complexity of O(n), where n is the length of the string.

Example
Input: ””abcda”” Output: ””a”” Input: ””abcd”” Output: null

Solution
c h a r f i r s t R e p e a t i n g C h a r = ’ \0 ’ ;
Map<Character , I n t e g e r > charIndexMap = new HashMap<>() ;
f o r ( i n t i = 0 ; i < s t r . l e n g t h ( ) ; i ++) {
c h a r c = s t r . charAt ( i ) ;
i f ( charIndexMap . c o n t a i n s K e y ( c ) ) {
firstRepeatingChar = c ;
break ;
} else {
charIndexMap . put ( c , i ) ;
}
}
return firstRepeatingChar ;

””
 75. Count Character Occurrences

Problem Description
Count the occurrences of a given character in a string. The input is a string and a character, and the output is the
number of times the character appears in the string.

Example
Input: string = ””hello world””, character = ’l’ Output: 3

Solution
s t r i n g = ” ” h e l l o world ” ”
character = ’ l ’
count = 0
f o r i in range ( len ( s t r i n g ) ) :
i f s t r i n g [ i ] == c h a r a c t e r :
count += 1
p r i n t ( count )

””
 76. Sort Characters by Frequency

Problem Description
Sort characters in a string by frequency in descending order. If two characters have the same frequency, sort them
by their ASCII value in ascending order. The input is a string of characters and the output is a string with
characters sorted by frequency.

Example
Input: ””tree”” Output: ””eert”” Input: ””cccaaa”” Output: ””aaaccc””

Solution
c h a r [ ] c h a r s = s t r . toCharArray ( ) ;
i n t [ ] f r e q = new i n t [ 2 5 6 ] ;
f o r ( char c : chars ) {
f r e q [ c ]++;
}
I n t e g e r [ ] i n d i c e s = new I n t e g e r [ 2 5 6 ] ;
f o r ( i n t i = 0 ; i < 2 5 6 ; i ++) {
indices [ i ] = i ;
}
Arrays . s o r t ( i n d i c e s , ( a , b ) −> {
i f ( f r e q [ a ] == f r e q [ b ] ) {
return a − b ;
} else {
return freq [ b ] − freq [ a ] ;
}
}) ;
S t r i n g B u i l d e r sb = new S t r i n g B u i l d e r ( ) ;
for ( int i : indices ) {
i f ( f r e q [ i ] > 0) {
f o r ( i n t j = 0 ; j < f r e q [ i ] ; j ++) {
sb . append ( ( c h a r ) i ) ;
}
}
}
r e t u r n sb . t o S t r i n g ( ) ;

””
 77. Palindrome Rearrangement Check

Problem Description
The problem requires checking if a given string can be rearranged into a palindrome. A palindrome is a string that
reads the same backward as forward. The approach to solve this problem is to count the frequency of each
character in the string and check if more than one character has an odd frequency. If a string can be rearranged
into a palindrome, it can have at most one character with an odd frequency.

Example
Consider the string ””aabbccee””. This string can be rearranged into a palindrome ””abcceecba”” or ””acebbcaa””
etc. However, the string ””aabbbcc”” cannot be rearranged into a palindrome because it has more than one
character with an odd frequency.

Solution
c h a r [ ] s t r = new c h a r [ ] { ’ a ’ , ’ a ’ , ’ b ’ , ’ b ’ , ’ c ’ , ’ c ’ , ’ e ’ , ’ e ’
};
i n t [ ] f r e q = new i n t [ 2 5 6 ] ; // assuming ASCII s i z e
i n t oddCount = 0 ;

f o r ( char c : s t r ) {
f r e q [ c ]++;
}

f o r ( i n t i = 0 ; i < 2 5 6 ; i ++) {
i f ( f r e q [ i ] % 2 != 0 ) {
oddCount++;
}
i f ( oddCount > 1 ) {
break ;
}
}

i f ( oddCount <= 1 ) {
System . out . p r i n t l n ( ” ”The s t r i n g can be r e a r r a n g e d i n t o a
palindrome . ”” ) ;
} else {
System . out . p r i n t l n ( ” ”The s t r i n g cannot be r e a r r a n g e d i n t o a
palindrome . ”” ) ;
}

””
 78. Most Frequent Element

Problem Description
The most frequent element algorithm finds the element that appears most frequently in a given array. The input is
an array of integers and the output is the most frequent element. If there are multiple elements with the same
highest frequency, any of them can be returned.

Example
Input: nums = [1,1,2,2,3,3,3] Output: 3 Input: nums = [1,2,2,3,3,3] Output: 3

Solution
Map<I n t e g e r , I n t e g e r > freqMap = new HashMap<>() ;
i n t maxFreq = 0 ;
i n t mostFrequent = nums [ 0 ] ;
f o r ( i n t num : nums ) {
i n t f r e q = freqMap . g e t O r D e f a u l t (num , 0 ) + 1 ;
freqMap . put (num , f r e q ) ;
i f ( f r e q > maxFreq ) {
maxFreq = f r e q ;
mostFrequent = num ;
}
}
r e t u r n mostFrequent ;

””
 79. Longest Substring without Repeating
Characters

Problem Description
The longest substring without repeating characters algorithm is designed to find the length of the longest substring
in a given string that does not contain any repeating characters. The input to this algorithm is a string, and the
output is the length of the longest substring without repeating characters. The algorithm should be able to handle
strings of varying lengths and should be efficient in terms of time complexity.

Example
For the input string ””abcabcbb””, the longest substring without repeating characters is ””abc”” with a length of
3. For the input string ””bbbbb””, the longest substring without repeating characters is ””b”” with a length of 1.
For the input string ””pwwkew””, the longest substring without repeating characters is ””wke”” with a length of 3.

Solution
int l e f t = 0;
i n t maxLength = 0 ;
j a v a . u t i l . HashSet<Character > c h a r S e t = new j a v a . u t i l . HashSet
<>() ;

f o r ( i n t r i g h t = 0 ; r i g h t < s . l e n g t h ( ) ; r i g h t ++) {
w h i l e ( c h a r S e t . c o n t a i n s ( s . charAt ( r i g h t ) ) ) {
c h a r S e t . remove ( s . charAt ( l e f t ) ) ;
l e f t ++;
}
c h a r S e t . add ( s . charAt ( r i g h t ) ) ;
maxLength = Math . max( maxLength , r i g h t − l e f t + 1 ) ;
}
r e t u r n maxLength ;

””
 80. Longest Repeated Non-Overlapping
Substring

Problem Description
The problem requires finding the longest repeated non-overlapping substring in a given string. The input is a string,
and the output should be the longest repeated non-overlapping substring. The string can contain any ASCII
characters. The goal is to identify the longest substring that appears at least twice in the string without overlapping.

Example
For the input string ””abcabcbb””, the expected output is ””abc”” because it is the longest repeated
non-overlapping substring. For the input string ””abcdefg””, the expected output is an empty string because there
are no repeated non-overlapping substrings.

Solution
int [ ] [ ] dp = new i n t [ s . l e n g t h ( ) ] [ s . l e n g t h ( ) ] ;
int maxLength = 0 ;
int endPos = 0 ;
for ( i n t i = 0 ; i < s . l e n g t h ( ) ; i ++) {
f o r ( i n t j = i + 1 ; j < s . l e n g t h ( ) ; j ++) {
i f ( s . charAt ( i ) == s . charAt ( j ) ) {
i f ( i == 0 ) {
dp [ i ] [ j ] = 1 ;
} else {
dp [ i ] [ j ] = dp [ i − 1 ] [ j − 1 ] + 1 ;
}
i f ( dp [ i ] [ j ] > maxLength ) {
maxLength = dp [ i ] [ j ] ;
endPos = j ;
}
}
}
}
S t r i n g r e s u l t = ”””” ;
i f ( maxLength > 0 ) {
r e s u l t = s . s u b s t r i n g ( endPos − maxLength + 1 , endPos + 1 ) ;
}

””
 81. Longest Common Prefix

Problem Description
The longest common prefix problem is a classic problem in computer science, where we are given an array of strings
and we need to find the longest common prefix among all the strings. The input is an array of strings, and the
output is the longest common prefix. The strings are compared character by character, and the comparison stops
when a mismatch is found or when the end of the shortest string is reached.

Example
The input array of strings is [””flower””,””flow””,””flight””]. The expected output is ””fl””. The input array of
strings is [””dog””,””racecar””,””car””]. The expected output is ””””.

Solution
S t r i n g longestCommonPrefix = ” ” ” ” ;
i f ( s t r s . l e n g t h == 0 ) {
r e t u r n longestCommonPrefix ;
}
f o r ( i n t i = 0 ; i < s t r s [ 0 ] . l e n g t h ( ) ; i ++) {
c h a r c = s t r s [ 0 ] . charAt ( i ) ;
f o r ( i n t j = 1 ; j < s t r s . l e n g t h ; j ++) {
i f ( i == s t r s [ j ] . l e n g t h ( ) | | s t r s [ j ] . charAt ( i ) != c ) {
r e t u r n longestCommonPrefix ;
}
}
longestCommonPrefix += c ;
}
r e t u r n longestCommonPrefix ;

””
 82. Longest Common Suffix

Problem Description
The problem requires finding the longest common suffix among a list of words. The input is a list of strings, and the
output is the longest common suffix. The algorithm should compare the words from the end to find the common
suffix.

Example
The input can be a list of words: [””abcde””, ””bcde””, ””cde””]. The expected output is ””cde”” since it is the
longest common suffix among the words.

Solution
words = [ ” ” abcde ” ” , ” ” bcde ” ” , ” ” cde ” ” ]
minLength = min ( l e n ( word ) f o r word i n words )
commonSuffix = ” ” ” ”
f o r i i n r a n g e ( 1 , minLength + 1 ) :
s u f f i x = words [ 0 ] [ − i ]
f o r word i n words [ 1 : ] :
i f word[− i ] != s u f f i x :
break
else :
commonSuffix = s u f f i x + commonSuffix
continue
break
p r i n t ( commonSuffix )

””
 83. Count Substrings Starting and Ending
with Same Character

Problem Description
The problem requires counting the number of substrings in a given string that start and end with the same
character. The input is a string of characters, and the output is the total count of such substrings. For each unique
character in the string, we can calculate the count of substrings starting and ending with that character using the
formula count * (count-1)/2, where count is the number of occurrences of the character in the string.

Example
Consider a sample string ””abcba””. The character ’a’ appears twice, so the count of substrings starting and ending
with ’a’ is 2 * (2-1)/2 = 1. The character ’b’ appears twice, so the count of substrings starting and ending with ’b’
is 2 * (2-1)/2 = 1. The character ’c’ appears once, so the count of substrings starting and ending with ’c’ is 1 *
(1-1)/2 = 0. The total count of substrings starting and ending with the same character is 1 + 1 + 0 = 2.

Solution
charCount = new HashMap<Character , I n t e g e r >() ;
f o r ( c h a r c : s . toCharArray ( ) ) {
i f ( charCount . c o n t a i n s K e y ( c ) ) {
charCount . put ( c , charCount . g e t ( c ) + 1 ) ;
} else {
charCount . put ( c , 1 ) ;
}
}
count = 0 ;
f o r ( i n t f r e q : charCount . v a l u e s ( ) ) {
count += f r e q ∗ ( f r e q − 1 ) / 2 ;
}

””
 84. Smallest Substring Containing All
Characters of Another

Problem Description
The problem requires finding the smallest substring in a given string that contains all characters of another string.
The input consists of two strings, and the output should be the smallest substring that meets the condition. The
algorithm should handle cases where no such substring exists.

Example
Given two strings, s1 = ””ADOBECODEBANC”” and s2 = ””ABC””, the smallest substring of s1 that contains all
characters of s2 is ””BANC””.

Solution
S t r i n g s 1 = ” ”ADOBECODEBANC” ” ;
S t r i n g s 2 = ” ”ABC” ” ;
i n t [ ] s2Count = new i n t [ 1 2 8 ] ;
i n t requiredChars = s2 . length ( ) ;
f o r ( c h a r c : s 2 . toCharArray ( ) ) {
s2Count [ c ]++;
r e q u i r e d C h a r s ++;
}
requiredChars = 0;
f o r ( i n t i = 0 ; i < 1 2 8 ; i ++) {
i f ( s2Count [ i ] > 0 ) {
r e q u i r e d C h a r s ++;
}
}
int l e f t = 0 , right = 0;
i n t formedChars = 0 ;
i n t [ ] windowCounts = new i n t [ 1 2 8 ] ;
i n t minLen = I n t e g e r .MAX VALUE;
S t r i n g minStr = ” ” ” ” ;
while ( r i g h t < s1 . length ( ) ) {
c h a r c = s 1 . charAt ( r i g h t ) ;
windowCounts [ c ]++;
i f ( s2Count [ c ] > 0 && windowCounts [ c ] == s2Count [ c ] ) {
formedChars++;
}
w h i l e ( l e f t <= r i g h t && formedChars == r e q u i r e d C h a r s ) {
c = s 1 . charAt ( l e f t ) ;
i f ( r i g h t − l e f t + 1 < minLen ) {
minLen = r i g h t − l e f t + 1 ;
minStr = s 1 . s u b s t r i n g ( l e f t , r i g h t + 1 ) ;
}
windowCounts [ c ]−−;
i f ( s2Count [ c ] > 0 && windowCounts [ c ] < s2Count [ c ] ) {
 formedChars −−;
}
l e f t ++;
}
r i g h t ++;
}

””
 85. Find All Substrings

Problem Description
Find all substrings of a given string. The input is a string of length n, and the output should be all possible
substrings. The string only contains lowercase English letters.

Example
Input: ””abc”” Output: [””a””, ””ab””, ””abc””, ””b””, ””bc””, ””c””]

Solution
S t r i n g s t r = ” ” abc ” ” ;
int n = str . length () ;
f o r ( i n t i = 0 ; i < n ; i ++) {
f o r ( i n t j = i ; j < n ; j ++) {
String s u b s t r i n g = s t r . s u b s t r i n g ( i , j + 1) ;
System . out . p r i n t l n ( s u b s t r i n g ) ;
}
}

””
 86. Substring Search

Problem Description
The substring search problem involves finding the first occurrence of a substring within a larger string. Given two
strings, haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part
of haystack. The input consists of two strings, and the output is the index of the first occurrence of the substring.

Example
For the input haystack = ””hello”” and needle = ””ll””, the expected output is 2, because ””ll”” first occurs at
index 2 in ””hello””. If the input is haystack = ””aaaaa”” and needle = ””bba””, the expected output is -1,
because ””bba”” is not a substring of ””aaaaa””.

Solution
i n t [ ] computePrefixFunction ( char [ ] needle ) {
i n t [ ] p r e f i x = new i n t [ n e e d l e . l e n g t h ] ;
int j = 0;
f o r ( i n t i = 1 ; i < n e e d l e . l e n g t h ; i ++) {
w h i l e ( j > 0 && n e e d l e [ j ] != n e e d l e [ i ] ) {
j = prefix [ j − 1];
}
i f ( n e e d l e [ j ] == n e e d l e [ i ] ) {
j ++;
}
prefix [ i ] = j ;
}
return prefix ;
}

i n t s t r S t r ( c h a r [ ] haystack , c h a r [ ] n e e d l e ) {
i f ( n e e d l e . l e n g t h == 0 ) {
return 0;
}
i n t [ ] p r e f i x = computePrefixFunction ( needle ) ;
int j = 0;
f o r ( i n t i = 0 ; i < h a y s t a c k . l e n g t h ; i ++) {
w h i l e ( j > 0 && h a y s t a c k [ i ] != n e e d l e [ j ] ) {
j = prefix [ j − 1];
}
i f ( h a y s t a c k [ i ] == n e e d l e [ j ] ) {
j ++;
}
i f ( j == n e e d l e . l e n g t h ) {
return i − needle . length + 1;
}
}
r e t u r n −1;
}

””
 87. Longest Palindromic Substring

Problem Description
The goal is to find the longest palindromic substring within a given string. A palindromic substring is one that
reads the same backward as forward. The input is a string, and the output should be the longest palindromic
substring. The algorithm should be efficient and scalable for large input strings.

Example
For the input string ””babad””, the expected output could be either ””bab”” or ””aba”” since both are the longest
palindromic substrings. For the input ””cbbd””, the expected output is ””bb””.

Solution
s = input s t r i n g
n = length of s
l o n g e s t p a l i nd r o m e = ””””
max length = 0

f o r i in range (n) :
# odd l e n g t h p a l i n d r o m e
left , right = i , i
w h i l e l e f t >= 0 and r i g h t < n and s [ l e f t ] == s [ r i g h t ] :
i f r i g h t − l e f t + 1 > max length :
max length = r i g h t − l e f t + 1
l o n g e s t p a l i n d r o m e = s [ l e f t : r i g h t +1]
l e f t −= 1
r i g h t += 1

# even l e n g t h p a l i n d r o m e
left , right = i , i + 1
w h i l e l e f t >= 0 and r i g h t < n and s [ l e f t ] == s [ r i g h t ] :
i f r i g h t − l e f t + 1 > max length :
max length = r i g h t − l e f t + 1
l o n g e s t p a l i n d r o m e = s [ l e f t : r i g h t +1]
l e f t −= 1
r i g h t += 1

output l o n g e s t p a l i n d r o m e

””
 88. Count Palindromic Substrings

Problem Description
Count the number of different palindromic substrings in a given string. A palindromic substring is a substring that
reads the same backward as forward. The input is a string of characters, and the output is the number of unique
palindromic substrings.

Example
For the input string ””abc””, there are 3 palindromic substrings: ””a””, ””b””, ””c””. For the input string
””aaa””, there are 3 palindromic substrings: ””a””, ””aa””, ””aaa””.

Solution
s = ” ” abc ” ” // i n p u t s t r i n g
n = s . length ()
count = 0
palindromes = s e t ()

f o r i in range (n) :
// odd l e n g t h p a l i n d r o m e
l, r = i, i
w h i l e l >= 0 and r < n and s [ l ] == s [ r ] :
p a l i n d r o m e = s [ l : r +1]
i f p a l i n d r o m e not i n p a l i n d r o m e s :
count += 1
p a l i n d r o m e s . add ( p a l i n d r o m e )
l −= 1
r += 1

// even l e n g t h p a l i n d r o m e
l, r = i, i + 1
w h i l e l >= 0 and r < n and s [ l ] == s [ r ] :
p a l i n d r o m e = s [ l : r +1]
i f p a l i n d r o m e not i n p a l i n d r o m e s :
count += 1
p a l i n d r o m e s . add ( p a l i n d r o m e )
l −= 1
r += 1

””
89. Smallest Palindrome by Inserting Characters

Problem Description
The problem requires finding the smallest palindrome that can be formed by inserting characters into a given string.
The approach involves using the Longest Common Subsequence (LCS) of the input string and its reverse. The
minimum number of insertions required to form a palindrome is given by the length of the input string minus the
length of the LCS of the input string and its reverse.

Example
Given a string ””abc””, the reverse of the string is ””cba””. The LCS of ””abc”” and ””cba”” is ””a”” or ””b”” or
””c”” (any single character), which has a length of 1. Therefore, the minimum number of insertions required to
form a palindrome is 3 - 1 = 2, resulting in a palindrome like ””abcba”” or ””acbca”” or ””abcbcba”” etc.

Solution
s = ” ” abc ” ” // i n p u t s t r i n g
r e v = r e v e r s e ( s ) // r e v e r s e o f i n p u t s t r i n g
m = length ( s )
n = length ( rev )
dp = new i n t [m + 1 ] [ n + 1 ]
f o r i from 0 t o m:
f o r j from 0 t o n :
i f i == 0 o r j == 0 :
dp [ i ] [ j ] = 0
e l i f s [ i − 1 ] == r e v [ j − 1 ] :
dp [ i ] [ j ] = dp [ i − 1 ] [ j − 1 ] + 1
else :
dp [ i ] [ j ] = max( dp [ i − 1 ] [ j ] , dp [ i ] [ j − 1 ] )
l c s l e n g t h = dp [m] [ n ]
min insertions = m − lcs length
r e s u l t = ””””
i =m
j = n
w h i l e i > 0 and j > 0 :
i f s [ i − 1 ] == r e v [ j − 1 ] :
result = s [ i − 1] + result
i −= 1
j −= 1
e l i f dp [ i − 1 ] [ j ] > dp [ i ] [ j − 1 ] :
result = s [ i − 1] + result
i −= 1
else :
r e s u l t = rev [ j − 1] + r e s u l t
j −= 1
while i > 0:
result = s [ i − 1] + result
i −= 1
while j > 0:
 r e s u l t = rev [ j − 1] + r e s u l t
j −= 1
print result

””
 90. Shortest Palindrome by Prepending

Problem Description
The problem requires finding the shortest palindrome that can be formed by prepending characters to a given
string. The input is a string, and the output is the shortest palindrome that can be formed. The approach involves
finding the longest prefix of the string that is also a suffix of its reverse.

Example
Given the string ””aacecaaaa””, the reverse of the string is ””aaaacecaa””. The longest prefix that is also a suffix of
the reverse is ””aaaceca””. However, to form a palindrome, we need to prepend the remaining characters of the
reverse, which are ””aaa”” (excluding the overlapping part), but in reverse order, resulting in ””aaa”” becoming
””aaa””. So the shortest palindrome is ””aaacecaaaa”” which is ””aaa”” + ””aacecaaaa””.

Solution
s = ”” aacecaaaa ””
rev = s [ : : − 1 ]
f o r i in range ( len ( s ) ) :
i f s . s t a r t s w i t h ( rev [ i : ] ) :
print ( rev [ : i ] [ : : − 1 ] + s )
break

””
 91. Alternating Vowel-Consonant Pattern
Checker

Problem Description
Check if a given string has an alternating vowel-consonant pattern. The input is a string of lowercase English
letters. The output should be true if the string has an alternating vowel-consonant pattern, and false otherwise. A
vowel is defined as one of the characters ’a’, ’e’, ’i’, ’o’, ’u’. A consonant is defined as any lowercase English letter
that is not a vowel.

Example
Input: ””aeiou”” Output: false Input: ””abcde”” Output: true

Solution
bool isVowel = true ;
c h a r [ ] c h a r s = s . toCharArray ( ) ;
f o r ( i n t i = 1 ; i < c h a r s . l e n g t h ; i ++) {
boolean currIsVowel = f a l s e ;
i f ( c h a r s [ i ] == ’ a ’ | | c h a r s [ i ] == ’ e ’ | | c h a r s [ i ] == ’ i ’
| | c h a r s [ i ] == ’ o ’ | | c h a r s [ i ] == ’ u ’ ) {
currIsVowel = true ;
}
i f ( c u r r I s V o w e l == i s V o w e l ) {
return f a l s e ;
}
isVowel = currIsVowel ;
}
return true ;

””
 92. String Compression

Problem Description
String compression using run-length encoding is a simple form of data compression in which a sequence of
consecutive identical characters is stored as a single character and count. The input is a string of characters, and
the output should be the compressed string. For example, ””AAABBB”” would become ””A3B3””. The input
string only contains uppercase and lowercase letters.

Example
The input string ””AAABBBCCC”” would result in the output ””A3B3C3””. Another example is ””ABC”” which
would remain ””ABC”” since there are no consecutive repeated characters.

Solution
S t r i n g B u i l d e r compressed = new S t r i n g B u i l d e r ( ) ;
char currentChar = ’ ’ ;
i n t currentCount = 0 ;
f o r ( c h a r c : s . toCharArray ( ) ) {
i f ( c == c u r r e n t C h a r ) {
c u r r e n t C o u n t++;
} else {
i f ( c u r r e n t C h a r != ’ ’ ) {
compressed . append ( c u r r e n t C h a r ) ;
compressed . append ( c u r r e n t C o u n t ) ;
}
currentChar = c ;
currentCount = 1 ;
}
}
i f ( c u r r e n t C h a r != ’ ’ ) {
compressed . append ( c u r r e n t C h a r ) ;
compressed . append ( c u r r e n t C o u n t ) ;
}
i f ( compressed . l e n g t h ( ) >= s . l e n g t h ( ) ) {
return s ;
} else {
r e t u r n compressed . t o S t r i n g ( ) ;
}

””
 93. Remove Adjacent Duplicates

Problem Description
The algorithm removes adjacent duplicates from a given string until no more duplicates are found. The input is a
string of characters, and the output is the resulting string after removing all adjacent duplicates. The algorithm
should be efficient and scalable for large input strings.

Example
Input: ””aaaabbbccd”” Output: ””d”” The algorithm removes adjacent duplicates, resulting in the final output
string.

Solution
c h a r [ ] s t a c k = new c h a r [ 1 0 0 0 0 ] ;
i n t top = −1;
c h a r [ ] c h a r s = i n p u t . toCharArray ( ) ;
f o r ( char c : chars ) {
i f ( top >= 0 && s t a c k [ top ] == c ) {
top −−;
} else {
s t a c k [++top ] = c ;
}
}
S t r i n g B u i l d e r r e s u l t = new S t r i n g B u i l d e r ( ) ;
f o r ( i n t i = 0 ; i <= top ; i ++) {
r e s u l t . append ( s t a c k [ i ] ) ;
}
return r e s u l t . toString () ;

””
 94. String Rotation Check

Problem Description
Check if two input strings are rotations of each other. A string is considered a rotation of another if it can be
obtained by shifting the characters of the other string in a circular manner. The algorithm should take two strings
as input and return a boolean indicating whether they are rotations of each other. The input strings will only
contain lowercase letters.

Example
Input: string1 = ””abcde””, string2 = ””cdeab”” Output: true Input: string1 = ””abcde””, string2 = ””abced””
Output: false

Solution
S t r i n g s 1 = ” ” abcde ” ” ;
S t r i n g s 2 = ” ” cdeab ” ” ;
boolean r e s u l t = f a l s e ;
i f ( s 1 . l e n g t h ( ) == s 2 . l e n g t h ( ) ) {
S t r i n g temp = s 1 + s 1 ;
i f ( temp . c o n t a i n s ( s 2 ) ) {
r e s u l t = true ;
}
}
System . out . p r i n t l n ( r e s u l t ) ;

””
 95. Minimum Rotations to Match Strings

Problem Description
The problem requires finding the minimum number of rotations needed to match two given strings. The strings are
considered matched if one string is a rotation of the other. The input consists of two strings, and the output is the
minimum number of rotations required to match the strings. If the strings cannot be matched, the output should
indicate this.

Example
Consider two strings, ””abcde”” and ””cdeab””. The minimum number of rotations to match these strings is 2, as
””abcde”” can be rotated to ””cdeab”” by two rotations.

Solution
s t r 1 = ” ” abcde ” ”
s t r 2 = ” ” cdeab ” ”
i f l e n ( s t r 1 ) != l e n ( s t r 2 ) :
p r i n t ( ” ” S t r i n g s cannot be matched ” ” )
else :
rotations = 0
w h i l e s t r 1 != s t r 2 and r o t a t i o n s < l e n ( s t r 1 ) :
str1 = str1 [ 1 : ] + str1 [0]
r o t a t i o n s += 1
i f s t r 1 == s t r 2 :
print ( rotations )
else :
p r i n t ( ” ” S t r i n g s cannot be matched ” ” )

””
 96. Lexicographically Smallest Rotation

Problem Description
The problem requires finding the lexicographically smallest rotation of a given string. The input is a string of
characters, and the output is the lexicographically smallest rotation of the input string. A rotation of a string is
obtained by moving the last character to the front of the string.

Example
The input string is ””bcda””. The expected output is ””abcd”” because ””abcd”” is the lexicographically smallest
rotation of ””bcda””.

Solution
S t r i n g s = ” ” bcda ” ” ;
String smallest = s ;
f o r ( i n t i = 0 ; i < s . l e n g t h ( ) ; i ++) {
String rotated = s . substring ( i ) + s . substring (0 , i ) ;
i f ( r o t a t e d . compareTo ( s m a l l e s t ) < 0 ) {
smallest = rotated ;
}
}
System . out . p r i n t l n ( s m a l l e s t ) ;

””
 97. Lexicographically Next Permutation

Problem Description
The algorithm generates the lexicographically next permutation of a given sequence of numbers. Input: An array of
integers representing the current permutation. Output: The lexicographically next permutation of the input array.

Example
Input: [1, 2, 3] Output: [1, 3, 2] Input: [3, 2, 1] Output: [1, 2, 3]

Solution
i n t [ ] nextPermutation = new i n t [ nums . l e n g t h ] ;
System . a r r a y c o p y ( nums , 0 , nextPermutation , 0 , nums . l e n g t h ) ;
i n t i = nextPermutation . l e n g t h − 2 ;
w h i l e ( i >= 0 && nextPermutation [ i ] >= nextPermutation [ i + 1 ] )
{
i −−;
}
i f ( i >= 0 ) {
i n t j = nextPermutation . l e n g t h − 1 ;
w h i l e ( nextPermutation [ j ] <= nextPermutation [ i ] ) {
j −−;
}
i n t temp = nextPermutation [ i ] ;
nextPermutation [ i ] = nextPermutation [ j ] ;
nextPermutation [ j ] = temp ;
}
int l e f t = i + 1;
i n t r i g h t = nextPermutation . l e n g t h − 1 ;
while ( l e f t < right ) {
i n t temp = nextPermutation [ l e f t ] ;
nextPermutation [ l e f t ] = nextPermutation [ r i g h t ] ;
nextPermutation [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}

””
 98. String Subsequence Check

Problem Description
The goal is to determine if one string is a subsequence of another. A subsequence is a sequence that can be derived
from another sequence by deleting some elements without changing the order of the remaining elements. The input
consists of two strings, and the output is a boolean value indicating whether the first string is a subsequence of the
second.

Example
Consider the strings ””abc”” and ””ahbgdc””. The string ””abc”” is a subsequence of ””ahbgdc”” because we can
derive ””abc”” by removing some characters from ””ahbgdc”” without changing the order of the remaining
characters. On the other hand, ””axc”” is not a subsequence of ””ahbgdc”” because there is no way to derive
””axc”” by removing characters from ””ahbgdc”” while preserving the order.

Solution
int i = 0 , j = 0;
boolean isSubsequence = true ;
w h i l e ( i < s 1 . l e n g t h ( ) && j < s 2 . l e n g t h ( ) ) {
i f ( s 1 . charAt ( i ) == s 2 . charAt ( j ) ) {
i ++;
}
j ++;
}
i f ( i == s 1 . l e n g t h ( ) ) {
isSubsequence = true ;
} else {
isSubsequence = f a l s e ;
}
return isSubsequence ;

””
 99. Minimum Swaps to Make Strings
Identical

Problem Description
The problem requires finding the minimum number of swaps to make two strings identical. The strings are of the
same length and contain distinct characters. The input consists of two strings, and the output is the minimum
number of swaps required. The approach involves counting the mismatches and swappable pairs between the two
strings.

Example
Consider two strings ””abc”” and ””bac””. The expected output is 1, as only one swap is required to make the
strings identical. Another example is ””abcd”” and ””adcb””, which requires 2 swaps.

Solution
S t r i n g s t r 1 = ” ” abc ” ” ;
S t r i n g s t r 2 = ” ” bac ” ” ;
int n = str1 . length () ;
i n t mismatches = 0 ;
b o o l e a n [ ] v i s i t e d = new b o o l e a n [ n ] ;
f o r ( i n t i = 0 ; i < n ; i ++) {
i f ( s t r 1 . charAt ( i ) != s t r 2 . charAt ( i ) ) {
mismatches++;
}
}
i n t swaps = 0 ;
f o r ( i n t i = 0 ; i < n ; i ++) {
i f ( s t r 1 . charAt ( i ) != s t r 2 . charAt ( i ) && ! v i s i t e d [ i ] ) {
c h a r ch = s t r 1 . charAt ( i ) ;
f o r ( i n t j = i + 1 ; j < n ; j ++) {
i f ( s t r 1 . charAt ( j ) == s t r 2 . charAt ( i ) && s t r 2 . charAt
( j ) == ch && ! v i s i t e d [ j ] ) {
v i s i t e d [ j ] = true ;
swaps++;
break ;
}
}
}
}
System . out . p r i n t l n ( swaps ) ;

””
 100. Word Match by Swapping

Problem Description
This algorithm checks if two words can match by swapping two letters. It takes two strings as input and returns a
boolean value indicating whether the words can be matched. The input strings are expected to be of the same
length. The algorithm counts the character differences between the two strings and checks if swapping two letters
can make them match.

Example
The input strings are ””bank”” and ””kanb””. The expected output is true, because swapping the first and last
letters of ””bank”” results in ””kanb””. Another example is the input strings ””hello”” and ””hlleo””, where the
expected output is false, because no single swap can make them match.

Solution
S t r i n g word1 = ” ” bank ” ” ;
S t r i n g word2 = ” ” kanb ” ” ;
b o o l e a n canMatch = f a l s e ;
i f ( word1 . l e n g t h ( ) == word2 . l e n g t h ( ) ) {
int diffCount = 0;
i n t [ ] d i f f I n d e x e s = new i n t [ 2 ] ;
f o r ( i n t i = 0 ; i < word1 . l e n g t h ( ) ; i ++) {
i f ( word1 . charAt ( i ) != word2 . charAt ( i ) ) {
diffIndexes [ diffCount ] = i ;
d i f f C o u n t ++;
i f ( diffCount > 2) {
break ;
}
}
}
i f ( d i f f C o u n t == 2 ) {
i f ( word1 . charAt ( d i f f I n d e x e s [ 0 ] ) == word2 . charAt (
diffIndexes [1])
&& word1 . charAt ( d i f f I n d e x e s [ 1 ] ) == word2 . charAt (
diffIndexes [0]) ) {
canMatch = t r u e ;
}
} e l s e i f ( d i f f C o u n t == 0 ) {
canMatch = t r u e ;
}
}
System . out . p r i n t l n ( canMatch ) ;

””
 101. Word Break Problem

Problem Description
The word break problem is a classic problem in computer science and coding interviews. Given a non-empty string
s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a
space-separated sequence of one or more dictionary words. The input string s is left-aligned and the output is a
boolean value indicating whether the string can be segmented or not.

Example
The input string s = ””leetcode”” and the dictionary wordDict = [””leet””, ””code””] should return true because
””leetcode”” can be segmented into ””leet code””. Another example is the input string s = ””applepenapple”” and
the dictionary wordDict = [””apple””, ””pen””] which should return true because ””applepenapple”” can be
segmented into ””apple pen apple””.

Solution
b o o l e a n canBreak = f a l s e ;
int n = s . length () ;
b o o l e a n [ ] dp = new b o o l e a n [ n + 1 ] ;
dp [ 0 ] = t r u e ;
f o r ( i n t i = 1 ; i <= n ; i ++) {
f o r ( i n t j = 0 ; j < i ; j ++) {
i f ( dp [ j ] && wordDict . c o n t a i n s ( s . s u b s t r i n g ( j , i ) ) ) {
dp [ i ] = t r u e ;
break ;
}
}
}
canBreak = dp [ n ] ;

””
 102. Minimum Window Substring

Problem Description
The minimum window substring problem is a classic problem in computer science, where we are given a string and a
target string, and we need to find the minimum window in the string that contains all characters of the target string.
The input consists of two strings, the source string and the target string. The output is the minimum window
substring that contains all characters of the target string. If no such window exists, the output is an empty string.

Example
Consider the source string ””ADOBECODEBANC”” and the target string ””ABC””. The minimum window
substring that contains all characters of the target string is ””BANC””.

Solution
s = ” ”ADOBECODEBANC” ”
t = ” ”ABC” ”
tCount = {}
f o r char in t :
i f c h a r i n tCount :
tCount [ c h a r ] += 1
else :
tCount [ c h a r ] = 1
r e q u i r e d = l e n ( tCount )
left = 0
right = 0
formed = 0
windowCounts = {}
ans = f l o a t ( ” ” i n f ” ” ) , None , None
while right < len ( s ) :
character = s [ right ]
windowCounts [ c h a r a c t e r ] = windowCounts . g e t ( c h a r a c t e r ,
0) + 1
i f c h a r a c t e r i n tCount and windowCounts [ c h a r a c t e r ] ==
tCount [ c h a r a c t e r ] :
formed += 1
w h i l e l e f t <= r i g h t and formed == r e q u i r e d :
character = s [ l e f t ]
i f r i g h t − l e f t + 1 < ans [ 0 ] :
ans = ( r i g h t − l e f t + 1 , l e f t , r i g h t )
windowCounts [ c h a r a c t e r ] −= 1
i f c h a r a c t e r i n tCount and windowCounts [ c h a r a c t e r ]
< tCount [ c h a r a c t e r ] :
formed −= 1
l e f t += 1
r i g h t += 1
r e t u r n ” ” ” ” i f ans [ 0 ] == f l o a t ( ” ” i n f ” ” ) e l s e s [ ans [ 1 ] : ans
[ 2 ] + 1]
””
 103. Edit Distance

Problem Description
The edit distance between two strings is the minimum number of operations (substitutions, insertions, deletions)
required to change one string into another. Given two strings, find the edit distance between them. The input
consists of two strings, and the output is the edit distance between them.

Example
Input: str1 = ””kitten””, str2 = ””sitting”” Output: 3 Explanation: The edit distance between ””kitten”” and
””sitting”” is 3, as we can change ””kitten”” to ””sitting”” by substituting ’k’ with ’s’, substituting ’e’ with ’i’, and
appending ’g’.

Solution
m = str1 . length
n = str2 . length
dp = new i n t [m + 1 ] [ n + 1 ]
f o r i i n r a n g e (m + 1 ) :
dp [ i ] [ 0 ] = i
f o r j in range (n + 1) :
dp [ 0 ] [ j ] = j
f o r i in range (1 , m + 1) :
f o r j in range (1 , n + 1) :
i f s t r 1 [ i − 1 ] == s t r 2 [ j − 1 ] :
dp [ i ] [ j ] = dp [ i − 1 ] [ j − 1 ]
else :
dp [ i ] [ j ] = 1 + min ( dp [ i − 1 ] [ j − 1 ] , dp [ i − 1 ] [ j ] ,
dp [ i ] [ j − 1 ] )
e d i t d i s t a n c e = dp [m] [ n ]

””
 104. Regular Expression Matching

Problem Description
The regular expression matching algorithm is used to match a string with a pattern that may contain wildcards.
The pattern can contain two special characters: ’ ?’ which matches any single character, and ’*’ which matches any
sequence of characters, including an empty sequence. The task is to determine whether the given string matches the
pattern. The input consists of two strings: the string to be matched and the pattern. The output is a boolean value
indicating whether the string matches the pattern.

Example
The input string is ””aa”” and the pattern is ””a*””. The expected output is true, because the ’*’ in the pattern
can match any sequence of characters, including ””a””. Another example is the input string ””ab”” and the pattern
””a?b””, where the expected output is true, because the ’ ?’ in the pattern can match any single character,
including ””a””.

Solution
b o o l isMatch = f a l s e ;
int stringLength = s . length () ;
i n t patternLength = p . length ( ) ;
b o o l [ ] [ ] dp = new b o o l [ s t r i n g L e n g t h + 1 ] [ p a t t e r n L e n g t h + 1 ] ;
dp [ s t r i n g L e n g t h ] [ p a t t e r n L e n g t h ] = t r u e ;
f o r ( i n t i = s t r i n g L e n g t h ; i >= 0 ; i −−) {
f o r ( i n t j = p a t t e r n L e n g t h − 1 ; j >= 0 ; j −−) {
b o o l f i r s t m a t c h = ( i < s t r i n g L e n g t h && ( p . charAt ( j ) ==
s . charAt ( i ) | | p . charAt ( j ) == ’ ? ’ ) ) ;
i f ( j + 1 < p a t t e r n L e n g t h && p . charAt ( j + 1 ) == ’ ∗ ’ ) {
dp [ i ] [ j ] = dp [ i ] [ j + 2 ] | | f i r s t m a t c h && dp [ i +
1][ j ];
} else {
dp [ i ] [ j ] = f i r s t m a t c h && dp [ i + 1 ] [ j + 1 ] ;
}
}
}
isMatch = dp [ 0 ] [ 0 ] ;

””
 105. Count Distinct Subsequences

Problem Description
Count the distinct subsequences of a target string that appear in a source string. The input consists of two strings,
the source and the target. The output is the number of distinct subsequences of the target string that appear in the
source string.

Example
Input: source = ””rabbbit””, target = ””rabbit”” Output: 3 Explanation: There are three distinct subsequences of
””rabbit”” in ””rabbbit””: ””r-a-b-b-i-t””, ””r-a–b-b-i-t””, and ””r-a-b-b–i-t””.

Solution
i n t count = 0 ;
S t r i n g source = ”” rabbbit ”” ;
S t r i n g t a r g e t = ”” r a b b i t ”” ;
i n t [ ] [ ] dp = new i n t [ s o u r c e . l e n g t h ( ) + 1 ] [ t a r g e t . l e n g t h ( ) + 1 ] ;
f o r ( i n t i = 0 ; i <= s o u r c e . l e n g t h ( ) ; i ++) {
dp [ i ] [ 0 ] = 1 ;
}
f o r ( i n t i = 1 ; i <= s o u r c e . l e n g t h ( ) ; i ++) {
f o r ( i n t j = 1 ; j <= t a r g e t . l e n g t h ( ) ; j ++) {
i f ( s o u r c e . charAt ( i − 1 ) == t a r g e t . charAt ( j − 1 ) ) {
dp [ i ] [ j ] = dp [ i − 1 ] [ j − 1 ] + dp [ i − 1 ] [ j ] ;
} else {
dp [ i ] [ j ] = dp [ i − 1 ] [ j ] ;
}
}
}
count = dp [ s o u r c e . l e n g t h ( ) ] [ t a r g e t . l e n g t h ( ) ] ;

””
 106. Keypad Combinations

Problem Description
The problem requires generating all possible combinations of letters that a number could represent, given a
standard telephone keypad mapping. The input is a string of digits, and the output should be a list of all possible
combinations. The keypad mapping is as follows: 2 -¿ abc, 3 -¿ def, 4 -¿ ghi, 5 -¿ jkl, 6 -¿ mno, 7 -¿ pqrs, 8 -¿ tuv, 9
-¿ wxyz.

Example
For the input ””23””, the expected output is [””ad””, ””ae””, ””af””, ””bd””, ””be””, ””bf””, ””cd””, ””ce””,
””cf””]. This is because the digit 2 can be replaced with ””a””, ””b””, or ””c””, and the digit 3 can be replaced
with ””d””, ””e””, or ””f””.

Solution
S t r i n g [ ] mapping = { ” ” ” ” , ” ” ” ” , ” ” abc ” ” , ” ” d e f ” ” , ” ” g h i ” ” , ” ”
j k l ” ” , ” ”mno” ” , ” ” p q r s ” ” , ” ” tuv ” ” , ” ”wxyz” ” } ;
L i s t <S t r i n g > r e s u l t = new A r r a y L i s t <>() ;
b a c k t r a c k ( r e s u l t , ” ” ” ” , 0 , ” ” 23 ” ” ) ;
for ( String str : result ) {
System . out . p r i n t l n ( s t r ) ;
}

v o i d b a c k t r a c k ( L i s t <S t r i n g > r e s u l t , S t r i n g c u r r e n t , i n t index ,

String digi ts ) {
i f ( i n d e x == d i g i t s . l e n g t h ( ) ) {
r e s u l t . add ( c u r r e n t ) ;
return ;
}
S t r i n g l e t t e r s = mapping [ d i g i t s . charAt ( i n d e x ) − ’ 0 ’ ] ;
f o r ( c h a r l e t t e r : l e t t e r s . toCharArray ( ) ) {
backtrack ( r e s u l t , current + l e t t e r , index + 1 , d i g i t s ) ;
}
}

””
 107. String to Keypad Digit Sequence

Problem Description
The problem requires converting a given string into a keypad digit sequence. The keypad layout is assumed to be
the standard QWERTY keypad layout. The algorithm should map each character in the string to its corresponding
digit on the keypad. The input is a string of characters, and the output is the digit sequence corresponding to the
input string.

Example
The input string ””hello”” should be converted to the digit sequence ””4433555”” based on the standard keypad
layout, where ’h’ corresponds to ’4’, ’e’ to ’3’, ’l’ to ’5’, ’l’ to ’5’, and ’o’ to ’6’ but since there is no ’o’ on the ’6’ key,
we look at the keypad and see that ’o’ is on the ’6’ key along with ’m’ and ’n’, however ’o’ is the only vowel on that
key so it is the second letter on the key, hence ’o’ is ’6’ on most keypads but on some it could be ’66’ to type ’o’, for
this example we will use ’6’ for ’o’ and other letters follow similar logic.

Solution
c h a r [ ] mapping = { ’ 2 ’ , ’ 2 ’ , ’ 2 ’ , ’ 3 ’ , ’ 3 ’ , ’ 3 ’ , ’ 4 ’ , ’ 4 ’ , ’ 4 ’ ,
’5 ’ , ’5 ’ , ’5 ’ , ’6 ’ , ’6 ’ , ’6 ’ , ’7 ’ , ’7 ’ , ’7 ’ , ’7 ’ , ’8 ’ , ’8 ’ ,
’8 ’ , ’9 ’ , ’9 ’ , ’9 ’ , ’9 ’ };
S t r i n g r e s u l t = ”””” ;
f o r ( c h a r c : i n p u t S t r i n g . toCharArray ( ) ) {
i f ( c >= ’ a ’ && c <= ’ z ’ ) {
r e s u l t += mapping [ c − ’ a ’ ] ;
}
}
return r e s u l t ;

””
 108. Count Distinct Elements in Array

Problem Description
Count the number of distinct elements in a given array. The input is an array of integers and the output should be
the number of unique elements. The array can contain duplicate values and the task is to identify and count the
distinct elements.

Example
Input: [1, 2, 3, 2, 4, 5, 6, 2, 3] Output: 6 The distinct elements in the array are 1, 2, 3, 4, 5, 6.

Solution
Set<I n t e g e r > uniqueElements = new HashSet <>() ;
i n t count = 0 ;
f o r ( i n t num : nums ) {
i f ( uniqueElements . add (num) ) {
count++;
}
}
r e t u r n count ;

””
 109. Word Frequency Counter

Problem Description
The task is to count the frequency of each word in a given sentence. The input is a string of words separated by
spaces, and the output should be a dictionary or map where the keys are the unique words and the values are their
respective frequencies. The algorithm should be case-insensitive and ignore punctuation.

Example
Input: ””This is a test sentence, and this sentence is just a test.”” Output: this: 2, is: 2, a: 2, test: 2, sentence: 2,
and: 1, just: 1

Solution
map = new HashMap () ;
words = sentence . toLowerCase () . split ( " " [^ a - z ]+ " " ) ;
for ( word : words ) {
if (! word . isEmpty () ) {
if ( map . containsKey ( word ) ) {
map . put ( word , map . get ( word ) + 1) ;
} else {
map . put ( word , 1) ;
}
}
}
return map ;

””
 110. Find Element Appearing Exactly Once

Problem Description
Find an element that appears exactly once in a given array, all other elements appear exactly twice. The input is an
array of integers and the output is the integer that appears exactly once. The array will contain at least one
element and at most 10000 elements.

Example
Input:
[2 3 5 4 5 3 4]

Output: 2

Solution
i n t singleNumber = 0 ;
HashMap<I n t e g e r , I n t e g e r > frequencyMap = new HashMap<>() ;
f o r ( i n t num : nums ) {
frequencyMap . put (num , frequencyMap . g e t O r D e f a u l t (num , 0 ) +
1) ;
}
f o r (Map . Entry<I n t e g e r , I n t e g e r > e n t r y : frequencyMap . e n t r y S e t
() ) {
i f ( e n t r y . g e t V a l u e ( ) == 1 ) {
singleNumber = e n t r y . getKey ( ) ;
break ;
}
}
System . out . p r i n t l n ( singleNumber ) ;

””
 111. Find Element Appearing Exactly Twice

Problem Description
The problem requires finding an element that appears exactly twice in a given array or list of integers. The input is
a collection of integers, and the output should be the integer that occurs twice. If no such integer exists, the output
can be a default value or an indication that no such element was found. The algorithm should be efficient and
scalable for large inputs.

Example
Consider the input array: [2, 3, 5, 4, 5, 3, 4]. The expected output would be 5, as it is the only element that
appears exactly twice in the array. Another example could be the input array: [1, 2, 3, 4, 5], where the output
would indicate that no element appears exactly twice.

Solution
Map<I n t e g e r , I n t e g e r > frequencyMap = new HashMap<>() ;
f o r ( i n t num : nums ) {
frequencyMap . put (num , frequencyMap . g e t O r D e f a u l t (num , 0 ) +
1) ;
}
f o r (Map . Entry<I n t e g e r , I n t e g e r > e n t r y : frequencyMap . e n t r y S e t
() ) {
i f ( e n t r y . g e t V a l u e ( ) == 2 ) {
r e s u l t = e n t r y . getKey ( ) ;
break ;
}
}

””
 112. Most Frequent Element

Problem Description
The most frequent element algorithm finds the element that appears most frequently in a given array or list of
elements. The input is an array of integers and the output is the most frequent element. If there are multiple
elements with the same highest frequency, any one of them can be returned.

Example
For the input array [1, 2, 2, 3, 3, 3], the expected output is 3 because it appears most frequently. For the input
array [1, 1, 2, 2], either 1 or 2 can be returned as they both have the same highest frequency.

Solution
i n t maxCount = 0 ;
i n t mostFrequent = 0 ;
Map<I n t e g e r , I n t e g e r > countMap = new HashMap<>() ;

f o r ( i n t num : nums ) {
i n t count = countMap . g e t O r D e f a u l t (num , 0 ) + 1 ;
countMap . put (num , count ) ;
i f ( count > maxCount ) {
maxCount = count ;
mostFrequent = num ;
}
}
r e t u r n mostFrequent ;

””
 113. Group Elements by Frequency

Problem Description
The task is to group elements by their frequency in a given array. The input is an array of integers and the output
should be a map where the keys are the frequencies and the values are lists of integers that have that frequency.
The algorithm should be efficient and scalable.
Input: An array of integers Output: A map where keys are frequencies and values are lists of integers

Example
Input array: [1, 2, 2, 3, 3, 3, 4, 4, 4, 4] Expected output: 1: [1], 2: [2], 3: [3], 4: [4]

Solution
map = new HashMap ( ) ;
f o r ( i n t num : nums ) {
i f (map . c o n t a i n s K e y (num) ) {
map . put (num , map . g e t (num) + 1 ) ;
} else {
map . put (num , 1 ) ;
}
}
r e s u l t = new HashMap ( ) ;
f o r (Map . Entry e n t r y : map . e n t r y S e t ( ) ) {
i n t f r e q = ( i n t ) entry . getValue ( ) ;
i f ( ! r e s u l t . containsKey ( f r e q ) ) {
r e s u l t . put ( f r e q , new A r r a y L i s t ( ) ) ;
}
( ( A r r a y L i s t ) r e s u l t . g e t ( f r e q ) ) . add ( ( i n t ) e n t r y . getKey ( ) ) ;
}
return r e s u l t ;

””
 114. Two Sum Using HashMap

Problem Description
The two sum problem is a common coding challenge where you are given an array of integers and a target sum, and
you need to find two elements in the array that add up to the target sum. The input is an array of integers and a
target sum, and the output is an array of two indices of the elements that add up to the target sum. The array is
1-indexed, meaning the first element is at index 1.

Example
Given the input array [2, 7, 11, 15] and the target sum 9, the output would be [1, 2] because the elements at indices
1 and 2 (2 and 7) add up to 9.

Solution
i n t [ ] twoSum = new i n t [ 2 ] ;
HashMap<I n t e g e r , I n t e g e r > map = new HashMap<>() ;
i n t [ ] nums = new i n t [ ] { 2 , 7 , 1 1 , 1 5 } ;
int target = 9;
f o r ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {
i n t complement = t a r g e t − nums [ i ] ;
i f (map . c o n t a i n s K e y ( complement ) ) {
twoSum [ 0 ] = map . g e t ( complement ) + 1 ;
twoSum [ 1 ] = i + 1 ;
break ;
}
map . put ( nums [ i ] , i ) ;
}

””
 115. Pair with Given Difference

Problem Description
The problem requires finding a pair of elements in an array that have a given difference. The input is an array of
integers and a target difference, and the output is a pair of integers that have the given difference. The array can be
unsorted, and the difference can be positive or negative.

Example
For example, given the array [1, 7, 5, 9, 2] and a target difference of 3, the output would be (2, 5) or (5, 2) because
the difference between 2 and 5 is 3. Another example is the array [1, 2, 3, 4, 5] with a target difference of 1, where
the output would be (1, 2), (2, 3), (3, 4), or (4, 5).

Solution
i n t [ ] f i n d P a i r ( i n t [ ] nums , i n t d i f f ) {
Map<I n t e g e r , I n t e g e r > numMap = new HashMap<>() ;
f o r ( i n t num : nums ) {
i f (numMap . c o n t a i n s K e y (num − d i f f ) ) {
r e t u r n new i n t [ ] {num − d i f f , num } ;
}
i f (numMap . c o n t a i n s K e y (num + d i f f ) ) {
r e t u r n new i n t [ ] {num , num + d i f f } ;
}
numMap . put (num , num) ;
}
r e t u r n new i n t [ ] { } ;
}

””
 116. Find Subarray with Zero Sum

Problem Description
Find a subarray with a sum of zero in a given array of integers. The input is an array of integers and the output
should be the subarray with a sum of zero if it exists, otherwise an empty array or a message indicating no such
subarray exists. The algorithm should be efficient and scalable for large inputs.

Example
Input array: [-3, 2, 3, 1, 6, -2, -1, 4, -5] Expected output: One possible subarray with zero sum is [-2, -1, 4, -1] or
any other valid subarray, but for simplicity, we can return the first occurrence which could be [-3, 2, 3] or any other
valid subarray depending on the implementation.

Solution
i n t [ ] findZeroSumSubarray ( i n t [ ] nums ) {
i n t n = nums . l e n g t h ;
i n t [ ] prefixSum = new i n t [ n + 1 ] ;
HashMap<I n t e g e r , I n t e g e r > sumIndexMap = new HashMap<>() ;
sumIndexMap . put ( 0 , −1) ;
i n t currentSum = 0 ;
f o r ( i n t i = 0 ; i < n ; i ++) {
currentSum += nums [ i ] ;
prefixSum [ i + 1 ] = currentSum ;
i f ( sumIndexMap . c o n t a i n s K e y ( currentSum ) ) {
r e t u r n Arrays . copyOfRange ( nums , sumIndexMap . g e t (
currentSum ) + 1 , i + 1 ) ;
} else {
sumIndexMap . put ( currentSum , i ) ;
}
}
r e t u r n new i n t [ 0 ] ;
}

””
 117. Longest Subarray with Sum K

Problem Description
The problem requires finding the longest subarray in a given array with a sum equal to a target value k. The input
is an array of integers and the target sum k. The output should be the length of the longest subarray with sum k. If
no such subarray exists, the output should be 0.

Example
For the input array [1, 4, 20, 3, 10, 5] and target sum 33, the longest subarray with sum 33 is [20, 3, 10]. The
expected output is 3.

Solution
i n t maxLen = 0 ;
i n t prefixSum = 0 ;
HashMap<I n t e g e r , I n t e g e r > sumIndexMap = new HashMap<>() ;
sumIndexMap . put ( 0 , −1) ;
f o r ( i n t i = 0 ; i < nums . l e n g t h ; i ++) {
prefixSum += nums [ i ] ;
i f ( sumIndexMap . c o n t a i n s K e y ( prefixSum − k ) ) {
maxLen = Math . max( maxLen , i − sumIndexMap . g e t ( prefixSum
− k) ) ;
}
i f ( ! sumIndexMap . c o n t a i n s K e y ( prefixSum ) ) {
sumIndexMap . put ( prefixSum , i ) ;
}
}
r e t u r n maxLen ;

””
 118. Count Subarrays with Sum Equal to K

Problem Description
Count the number of subarrays in a given array that have a sum equal to k. The array can contain both positive
and negative integers. The input is an array of integers and an integer k, and the output is the number of subarrays
with sum equal to k.

Example
Input array: [1, 2, 3, 4, 5], k = 5 Expected output: 2 Explanation: The subarrays with sum equal to 5 are [2, 3] and
[5].

Solution
i n t countSubarrays = 0 ;
i n t [ ] a r r a y = new i n t [ ] { 1 , 2 , 3 , 4 , 5 } ;
int k = 5;
int n = array . length ;
HashMap<I n t e g e r , I n t e g e r > prefixSumCount = new HashMap<>() ;
i n t currentSum = 0 ;
prefixSumCount . put ( 0 , 1 ) ;
f o r ( i n t i = 0 ; i < n ; i ++) {
currentSum += a r r a y [ i ] ;
i f ( prefixSumCount . c o n t a i n s K e y ( currentSum − k ) ) {
c o u n t S u b a r r a y s += prefixSumCount . g e t ( currentSum − k ) ;
}
prefixSumCount . put ( currentSum , prefixSumCount . g e t O r D e f a u l t (
currentSum , 0 ) + 1 ) ;
}
return countSubarrays ;

””
 119. Longest Consecutive Sequence

Problem Description
The longest consecutive sequence problem involves finding the longest sequence of consecutive numbers in an
unsorted array of integers. The input is an array of integers, and the output is the length of the longest consecutive
sequence. The sequence can be either increasing or decreasing, but the numbers must be consecutive. The input
array may contain duplicate numbers, and the sequence should be composed of unique numbers.

Example
For the input array [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], and the output is 4. For the
input array [0, 3, 7, 2, 5, 8, 4, 6, 0, 1], the longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8], and the output is 9.

Solution
int longestConsecutive = 0;
HashSet<I n t e g e r > numSet = new HashSet <>() ;
f o r ( i n t num : nums ) {
numSet . add (num) ;
}
f o r ( i n t num : numSet ) {
i f ( ! numSet . c o n t a i n s (num − 1 ) ) {
i n t currentNum = num ;
int currentSequence = 1;
w h i l e ( numSet . c o n t a i n s ( currentNum + 1 ) ) {
currentNum += 1 ;
c u r r e n t S e q u e n c e += 1 ;
}
l o n g e s t C o n s e c u t i v e = Math . max( l o n g e s t C o n s e c u t i v e ,
currentSequence ) ;
}
}
return longestConsecutive ;

””
 120. Largest Subarray with Equal 0s and 1s

Problem Description
The problem requires finding the largest subarray with an equal number of 0s and 1s in a given binary array. The
input is a binary array containing 0s and 1s, and the output is the length of the largest subarray with an equal
number of 0s and 1s. The approach involves converting 0s to -1 and finding the longest subarray with a sum of 0.

Example
Consider the binary array [1, 0, 1, 0, 1, 0, 0, 1, 1]. The expected output is 8, which corresponds to the subarray [1,
0, 1, 0, 1, 0, 0, 1].

Solution
i n t maxLen = 0 ;
i n t [ ] a r r = new i n t [ ] { 1 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 1 } ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
i f ( a r r [ i ] == 0 ) {
a r r [ i ] = −1;
}
}
i n t sum = 0 ;
HashMap<I n t e g e r , I n t e g e r > map = new HashMap<>() ;
map . put ( 0 , −1) ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
sum += a r r [ i ] ;
i f (map . c o n t a i n s K e y ( sum ) ) {
maxLen = Math . max( maxLen , i − map . g e t ( sum ) ) ;
} else {
map . put ( sum , i ) ;
}
}

””
 121. Common Elements in Three Arrays

Problem Description
The problem requires finding the common elements in three given arrays. The input consists of three arrays of
integers, and the output should be a list of integers that are present in all three arrays. The algorithm should be
efficient and scalable for large inputs.

Example
Consider three arrays: [1, 5, 10, 20, 40, 80], [6, 7, 20, 80, 100], and [3, 4, 15, 20, 30, 70, 80, 120]. The common
elements in these arrays are [20, 80].

Solution
// I n i t i a l i z e s e t s for the three arrays
Set<I n t e g e r > s e t 1 = new HashSet <>() ;
Set<I n t e g e r > s e t 2 = new HashSet <>() ;
Set<I n t e g e r > s e t 3 = new HashSet <>() ;

// I n i t i a l i z e r e s u l t s e t t o s t o r e common e l e m e n t s
Set<I n t e g e r > r e s u l t = new HashSet <>() ;

// P o p u l a t e s e t s from i n p u t a r r a y s
f o r ( i n t num : a r r a y 1 ) {
s e t 1 . add (num) ;
}
f o r ( i n t num : a r r a y 2 ) {
s e t 2 . add (num) ;
}
f o r ( i n t num : a r r a y 3 ) {
s e t 3 . add (num) ;
}

// Find i n t e r s e c t i o n o f t h r e e s e t s
f o r ( I n t e g e r num : s e t 1 ) {
i f ( s e t 2 . c o n t a i n s (num) && s e t 3 . c o n t a i n s (num) ) {
r e s u l t . add (num) ;
}
}

// P r i n t or r e t u r n t h e r e s u l t
f o r ( I n t e g e r num : r e s u l t ) {
System . out . p r i n t (num + ” ” ” ” ) ;
}

””
 122. Smallest Subarray with All Distinct
Elements

Problem Description
The problem requires finding the smallest subarray in a given array that contains all distinct elements. The input is
an array of integers and the output is the length of the smallest subarray. The array can contain duplicate elements
and the distinct elements are not necessarily unique to the subarray.

Example
For the input array [1, 2, 3, 2, 1], the smallest subarray containing all distinct elements is [1, 2, 3] with a length of
3. For the input array [1, 1, 1, 1], the smallest subarray containing all distinct elements is [1] with a length of 1.

Solution
i n t m i n l e n g t h = I n t e g e r .MAX VALUE;
int l e f t = 0;
int distinct count = 0;
Map<I n t e g e r , I n t e g e r > freq map = new HashMap<>() ;

f o r ( i n t r i g h t = 0 ; r i g h t < a r r . l e n g t h ; r i g h t ++) {
i f ( freq map . g e t O r D e f a u l t ( a r r [ r i g h t ] , 0 ) == 0 ) {
d i s t i n c t c o u n t ++;
}
freq map . put ( a r r [ r i g h t ] , freq map . g e t O r D e f a u l t ( a r r [ r i g h t ] ,
0) + 1) ;

w h i l e ( d i s t i n c t c o u n t == a r r . l e n g t h && l e f t <= r i g h t ) {
m i n l e n g t h = Math . min ( m i n l e n g t h , r i g h t − l e f t + 1 ) ;
freq map . put ( a r r [ l e f t ] , freq map . g e t ( a r r [ l e f t ] ) − 1 ) ;
i f ( freq map . g e t ( a r r [ l e f t ] ) == 0 ) {
d i s t i n c t c o u n t −−;
}
l e f t ++;
}
}
return min length ;

””
 123. Array Rotation Check

Problem Description
Check if two given arrays are rotations of each other. Given two arrays A and B of size N, determine if they are
rotations of each other. The input consists of two arrays A and B, and the output is a boolean value indicating
whether they are rotations of each other.

Example
Consider the following example: Array A = [1, 2, 3, 4, 5], Array B = [3, 4, 5, 1, 2]. The expected output is true, as
Array B is a rotation of Array A.

Solution
Map<I n t e g e r , I n t e g e r > freqMap = new HashMap<>() ;
f o r ( i n t num : A) {
freqMap . put (num , freqMap . g e t O r D e f a u l t (num , 0 ) + 1 ) ;
}
f o r ( i n t num : B) {
i f ( ! freqMap . c o n t a i n s K e y (num) | | freqMap . g e t (num) == 0 ) {
break ;
}
freqMap . put (num , freqMap . g e t (num) − 1 ) ;
}
boolean isRotation = true ;
f o r ( i n t count : freqMap . v a l u e s ( ) ) {
i f ( count != 0 ) {
isRotation = f a l s e ;
break ;
}
}
i f ( i s R o t a t i o n && A. l e n g t h == B . l e n g t h ) {
System . out . p r i n t l n ( ” ” t r u e ” ” ) ;
} else {
System . out . p r i n t l n ( ” ” f a l s e ” ” ) ;
}

””
124. Smallest Range Covering Elements from
K Lists

Problem Description
The problem requires finding the smallest range that covers at least one element from each of the k sorted lists. The
input consists of k sorted lists of integers, and the output should be the smallest range in the form of [start, end]
that covers at least one element from each list.

Example
Consider the following three sorted lists: list1 = [4, 10, 15, 24, 26], list2 = [0, 9, 12, 20], list3 = [5, 18, 22, 30]. The
smallest range that covers at least one element from each list is [9, 12] since it includes the elements 10 from list1, 9
and 12 from list2, and no elements from list3 but the range [20, 22] would also work as it includes 20 from list2, 22
from list3, and 24 from list1, however [9, 12] is smaller.

Solution
P r i o r i t y Q u e u e <i n t [] > queue = new P r i o r i t y Q u e u e <>((a , b ) −>
a[0] − b[0]) ;
HashMap<I n t e g e r , I n t e g e r > countMap = new HashMap<>() ;
i n t [ ] p o i n t e r s = new i n t [ k ] ;
i n t s t a r t = I n t e g e r .MAX VALUE, end = I n t e g e r . MIN VALUE ;
f o r ( i n t i = 0 ; i < k ; i ++) {
queue . o f f e r ( new i n t [ ] { l i s t s [ i ] [ 0 ] , i , 0 } ) ;
s t a r t = Math . min ( s t a r t , l i s t s [ i ] [ 0 ] ) ;
end = Math . max( end , l i s t s [ i ] [ 0 ] ) ;
}
i n t r a n g e = I n t e g e r .MAX VALUE;
i n t [ ] r e s u l t = new i n t [ ] { −1, −1};
w h i l e ( ! queue . isEmpty ( ) ) {
i n t [ ] c u r r = queue . p o l l ( ) ;
i f ( end − s t a r t < r a n g e ) {
r a n g e = end − s t a r t ;
r e s u l t = new i n t [ ] { s t a r t , end } ;
}
i f ( curr [ 2 ] + 1 < l i s t s [ curr [ 1 ] ] . length ) {
queue . o f f e r ( new i n t [ ] { l i s t s [ c u r r [ 1 ] ] [ c u r r [ 2 ] + 1 ] ,
curr [ 1 ] , curr [ 2 ] + 1}) ;
end = Math . max( end , l i s t s [ c u r r [ 1 ] ] [ c u r r [ 2 ] + 1 ] ) ;
} else {
break ;
}
s t a r t = I n t e g e r .MAX VALUE;
f o r ( i n t i = 0 ; i < k ; i ++) {
s t a r t = Math . min ( s t a r t , l i s t s [ i ] [ p o i n t e r s [ i ] ] ) ;
}
}
””
 125. Prime Number Check

Problem Description
The algorithm checks whether a given number is prime or not. It takes an integer as input and returns a boolean
value indicating whether the number is prime. A prime number is a natural number greater than 1 that has no
positive divisors other than 1 and itself. The algorithm checks divisibility up to the square root of the number.
Input: An integer n Output: A boolean value indicating whether n is prime

Example
Input: 25 Output: false Input: 23 Output: true

Solution
i n t n = 0 ; // i n p u t number
boolean isPrime = true ;
i f ( n <= 1 ) {
isPrime = f a l s e ;
} else {
f o r ( i n t i = 2 ; i <= Math . s q r t ( n ) ; i ++) {
i f ( n % i == 0 ) {
isPrime = f a l s e ;
break ;
}
}
}
System . out . p r i n t l n ( i s P r i m e ) ;

””
 126. Sieve of Eratosthenes

Problem Description
The Sieve of Eratosthenes is an algorithm used to generate all primes up to a given number n. The algorithm works
by iteratively marking the multiples of each prime number starting from 2. The input is an integer n, and the
output is a list of all prime numbers up to n.

Example
Input: n = 30 Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Solution
b o o l [ ] prime = new b o o l [ n + 1 ] ;
f o r ( i n t i = 0 ; i <= n ; i ++) {
prime [ i ] = t r u e ;
}
prime [ 0 ] = prime [ 1 ] = f a l s e ;
f o r ( i n t p = 2 ; p ∗ p <= n ; p++) {
i f ( prime [ p ] ) {
f o r ( i n t i = p ∗ p ; i <= n ; i += p ) {
prime [ i ] = f a l s e ;
}
}
}
f o r ( i n t i = 2 ; i <= n ; i ++) {
i f ( prime [ i ] ) {
System . out . p r i n t ( i + ” ” ” ” ) ;
}
}

””
 127. Find Nth Prime Number

Problem Description
The algorithm is designed to find the nth prime number. The input is an integer n, representing the position of the
prime number to be found. The output will be the nth prime number. The algorithm will utilize the Sieve of
Eratosthenes approach to efficiently find prime numbers.

Example
For example, given n = 10, the output should be 29, as it is the 10th prime number. The input can be a single
integer, and the output will be a single integer representing the nth prime number.

Solution
i n t nthPrime = 0 ;
i n t count = 0 ;
i n t num = 2 ;
w h i l e ( count < n ) {
boolean isPrime = true ;
f o r ( i n t i = 2 ; i ∗ i <= num ; i ++) {
i f (num % i == 0 ) {
isPrime = f a l s e ;
break ;
}
}
i f ( isPrime ) {
count++;
nthPrime = num ;
}
num++;
}
System . out . p r i n t l n ( nthPrime ) ;

””
 128. Prime Factorization

Problem Description
The prime factorization of a number n is the expression of n as a product of prime numbers. This algorithm will
find the prime factors of a given number n. The input is an integer n, and the output will be the prime factors of n.

Example
For example, if the input is 315, the output will be 3 * 3 * 5 * 7, since 3 * 3 * 5 * 7 = 315.

Solution
i = 2
factors = [ ]
w h i l e i ∗ i <= n :
if n % i :
i += 1
else :
n //= i
f a c t o r s . append ( i )
i f n > 1:
f a c t o r s . append ( n )
result = 1
for factor in f a c t o r s :
r e s u l t ∗= f a c t o r
print ( factors )

””
 129. Check if Number is Power of 2

Problem Description
Check if a given number is a power of 2. The input is an integer n, and the output is a boolean value indicating
whether n is a power of 2 or not. The algorithm should handle all positive integers and return true if the number is
a power of 2, false otherwise.

Example
Input: n = 8 Output: true Input: n = 10 Output: false

Solution
i n t n = 8 ; // i n p u t number
bool r e s u l t = f a l s e ;
i f (n > 0) {
r e s u l t = ( n & ( n − 1 ) ) == 0 ;
}

””
 130. Check if Number is Power of 3

Problem Description
Check if a given number is a power of 3. The input is an integer, and the output should be a boolean value
indicating whether the number is a power of 3 or not. The algorithm should handle both positive and negative
numbers, as well as zero.

Example
Input: 27 Output: true Input: 12 Output: false

Solution
i n t n = 2 7 ; // i n p u t number
bool r e s u l t = f a l s e ;
i f (n > 0) {
w h i l e ( n % 3 == 0 ) {
n = n / 3;
}
i f ( n == 1 ) {
r e s u l t = true ;
}
}

””
 131. Count Digits in Number

Problem Description
Count the number of digits in a given integer. The input is a single integer, and the output should be the number of
digits in the integer. For example, the input 12345 should output 5.

Example
Input: 12345 Output: 5 Input: 10000 Output: 5 Input: 9 Output: 1

Solution
i n t count = 0 ;
i n t n = abs ( number ) ;
while (n > 0) {
n = n / 10;
count++;
}
i f ( number == 0 ) {
count = 1 ;
}

””
 132. Reverse Digits of Number

Problem Description
The algorithm takes an integer as input and returns the integer with its digits reversed. For example, if the input is
123, the output should be 321. The input is a 32-bit signed integer, and the output should also be a 32-bit signed
integer. If the reversed integer overflows, the function should return 0.

Example
Input: 123 Output: 321 Input: -456 Output: -654

Solution
int reverse = 0;
int sign = 1;
i n t num = 1 2 3 ; // i n p u t number
i f (num < 0 ) {
s i g n = −1;
num = num ∗ −1;
}
w h i l e (num > 0 ) {
i n t d i g i t = num % 1 0 ;
r e v e r s e = r e v e r s e ∗ 10 + d i g i t ;
num = num / 1 0 ;
}
reverse = reverse ∗ sign ;
i f ( r e v e r s e > 2147483647 | | r e v e r s e < −2147483648) {
reverse = 0;
}

””
 133. Palindrome Number Checker

Problem Description
Check if a given number is a palindrome. A palindrome number is a number that remains the same when its digits
are reversed. The algorithm should take an integer as input and return a boolean value indicating whether the
number is a palindrome or not. The input is a 32-bit signed integer and the output is a boolean value.

Example
Input: 121 Output: true Input: -121 Output: false Input: 10 Output: false

Solution
x = abs (num)
reve r s e d n u m = 0
w h i l e x != 0 :
d i g i t = x % 10
r e v e r s e d n u m = r e v er s e d n u m ∗ 10 + d i g i t
x = x // 10
r e t u r n r e v e r s e d n u m == abs (num)

””
 134. Armstrong Number Checker

Problem Description
The Armstrong number is a number that is equal to the sum of its own digits each raised to the power of the
number of digits. Given a number, check if it is an Armstrong number. The input is an integer and the output is a
boolean value indicating whether the number is an Armstrong number or not.

Example
For the input 153, the output is true because
13 +53 +33 = 1+125+27 = 153.F ortheinput1634, theoutputistruebecause14 +64 +34 +44 = 1+1296+81+256 = 1634.

Solution
i n t temp = n ;
int digitCount = 0;
w h i l e ( temp != 0 ) {
temp = temp / 1 0 ;
d i g i t C o u n t ++;
}
temp = n ;
i n t sum = 0 ;
w h i l e ( temp != 0 ) {
i n t d i g i t = temp % 1 0 ;
sum = sum + ( i n t ) Math . pow ( d i g i t , d i g i t C o u n t ) ;
temp = temp / 1 0 ;
}
i f ( n == sum ) {
return true ;
} else {
return f a l s e ;
}

””
 135. Finding GCD of Two Numbers

Problem Description
The problem requires finding the greatest common divisor (GCD) of two given integers. The GCD of two numbers
is the largest positive integer that divides both numbers without leaving a remainder. The input consists of two
integers, and the output is their GCD.

Example
For example, given two numbers 48 and 18, the expected output is 6, since 6 is the largest number that divides both
48 and 18 without leaving a remainder.

Solution
int a = 48; // first number
int b = 18; // second number
while ( b != 0) {
int temp = b ;
b = a % b;
a = temp ;
}
int gcd = a ; // gcd is stored in variable a after the loop

””
 136. Find LCM of Two Numbers

Problem Description
The algorithm is designed to find the Least Common Multiple (LCM) of two numbers. The LCM of two integers a
and b is the smallest positive integer that is divisible by both a and b. The input consists of two integers, and the
output is their LCM. The approach used here is based on the mathematical formula: LCM(a, b) = (a * b) /
GCD(a, b), where GCD is the Greatest Common Divisor.

Example
For example, given two numbers 12 and 15, the LCM would be 60 because 60 is the smallest number that both 12
and 15 can divide into evenly. The GCD of 12 and 15 is 3, so using the formula LCM(a, b) = (a * b) / GCD(a, b),
we get LCM(12, 15) = (12 * 15) / 3 = 60.

Solution
int a = 1 2 ; // f i r s t number
int b = 1 5 ; // second number
int gcd = 1 ; // i n i t i a l i z e gcd
for ( i n t i = 1 ; i <= a && i <= b ; i ++) {
i f ( a % i == 0 && b % i == 0 ) {
gcd = i ;
}
}
i n t lcm = ( a ∗ b ) / gcd ; // c a l c u l a t e lcm u s i n g t h e f o r m u l a

””
 137. Find LCM of Array

Problem Description
Find the Least Common Multiple (LCM) of all elements in a given array of integers. The input is an array of
integers and the output is the LCM of all elements in the array.

Example
Input: [2, 7, 3] Output: 42 Explanation: The LCM of 2, 7, and 3 is 42.

Solution
i n t lcm = nums [ 0 ] ;
f o r ( i n t i = 1 ; i < nums . l e n g t h ; i ++) {
lcm = ( lcm ∗ nums [ i ] ) / gcd ( lcm , nums [ i ] ) ;
}
i n t gcd ( i n t a , i n t b ) {
i f ( b == 0 ) {
return a ;
}
r e t u r n gcd ( b , a % b ) ;
}

””
 138. Modular Exponentiation

Problem Description
Modular exponentiation is a method for efficiently calculating the value of a number raised to a power in modular
arithmetic. The problem requires us to find the result of
ab modn, wherea, b, andnaregivenintegers.T heinputconsistsof threeintegers :
thebasea, theexponentb, andthemodulusn.T heoutputistheresultof ab modn.

Example
For example, given a = 2, b = 3, and n = 5, the output should be 3, because 23 mod5 = 8mod5 = 3.

Solution
int result = 1;
int base = a ;
int exponent = b ;
int modulus = n ;

w h i l e ( exponent > 0 ) {
i f ( exponent % 2 == 1 ) {
r e s u l t = ( r e s u l t ∗ b a s e ) % modulus ;
}
exponent = exponent / 2 ;
b a s e = ( b a s e ∗ b a s e ) % modulus ;
}

return r e s u l t ;

””
 139. Factorial of a Number

Problem Description
The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to
n. This algorithm calculates the factorial of a given number. The input is a single integer, and the output is the
factorial of that integer.

Example
For the input 5, the output should be 120, because 5! = 5 * 4 * 3 * 2 * 1 = 120. For the input 0, the output should
be 1, since the factorial of 0 is defined as 1.

Solution
int factorial = 1;
i n t n = 5 ; // i n p u t number
i f ( n == 0 ) {
factorial = 1;
} else {
f o r ( i n t i = 1 ; i <= n ; i ++) {
f a c t o r i a l ∗= i ;
}
}
System . out . p r i n t l n ( f a c t o r i a l ) ;

””
 140. Fibonacci Sequence Generation

Problem Description
The Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with
0 and 1. The problem requires generating the nth Fibonacci number using dynamic programming. The input is an
integer n, and the output is the nth Fibonacci number.

Example
For n = 10, the output should be 55, because the Fibonacci sequence up to the 10th number is: 0, 1, 1, 2, 3, 5, 8,
13, 21, 34, 55.

Solution
int n = 1 0 ; // i n p u t
int [ ] f i b = new i n t [ n + 1 ] ;
fib [ 0 ] = 0;
fib [ 1 ] = 1;
for ( i n t i = 2 ; i <= n ; i ++) {
fib [ i ] = fib [ i − 1] + fib [ i − 2 ] ;
}
int result = fib [n ] ;

””
 141. Find All Factors of N

Problem Description
Find all factors of a given number n. The algorithm should take an integer n as input and return a list of all factors
of n. The input is a single integer, and the output is a list of integers representing the factors of n.

Example
For example, given the input n = 12, the output should be [1, 2, 3, 4, 6, 12]. This is because the factors of 12 are 1,
2, 3, 4, 6, and 12.

Solution
i n t n = 1 2 ; // i n p u t number
L i s t <I n t e g e r > f a c t o r s = new A r r a y L i s t <>() ; // l i s t t o s t o r e
factors
f o r ( i n t i = 1 ; i <= Math . s q r t ( n ) ; i ++) {
i f ( n % i == 0 ) {
f a c t o r s . add ( i ) ;
i f ( n / i != i ) {
f a c t o r s . add ( n / i ) ;
}
}
}
C o l l e c t i o n s . s o r t ( f a c t o r s ) ; // s o r t t h e f a c t o r s i n a s c e n d i n g
order
System . out . p r i n t l n ( f a c t o r s ) ; // p r i n t t h e f a c t o r s

””
 142. Sum of Divisors

Problem Description
The algorithm calculates the sum of all divisors of a given number n. Input: An integer n. Output: The sum of all
divisors of n. The algorithm iterates through all numbers from 1 to n to find the divisors.

Example
Input: n = 12 Output: 28 Explanation: The divisors of 12 are 1, 2, 3, 4, 6, and 12. The sum of these divisors is 1 +
2 + 3 + 4 + 6 + 12 = 28.

Solution
i n t sum = 0 ;
f o r ( i n t i = 1 ; i <= n ; i ++) {
i f ( n % i == 0 ) {
sum += i ;
}
}
r e t u r n sum ;

””
 143. Count Composites in Array

Problem Description
Count the number of composite numbers in a given array of integers. A composite number is a positive integer that
has at least one positive divisor other than one or itself. The input is an array of integers and the output is the
count of composite numbers in the array.

Example
Input array: [4, 6, 3, 12, 9, 2, 7, 10] Expected output: 5

Solution
i n t count = 0 ;
f o r ( i n t i = 0 ; i < a r r . l e n g t h ; i ++) {
boolean isPrime = true ;
i f ( arr [ i ] > 1) {
f o r ( i n t j = 2 ; j ∗ j <= a r r [ i ] ; j ++) {
i f ( a r r [ i ] % j == 0 ) {
isPrime = f a l s e ;
break ;
}
}
i f ( ! isPrime ) {
count++;
}
}
}
r e t u r n count ;

””
 144. Binary Exponentiation

Problem Description
The binary exponentiation algorithm is used to compute the value of a number raised to a power. Given a base and
an exponent, the algorithm calculates the result using the binary representation of the exponent. The input consists
of two integers, the base and the exponent, and the output is the result of the exponentiation.

Example
For example, given the base 2 and the exponent 3, the output should be 8. The algorithm should handle both
positive and negative exponents, as well as zero.

Solution
int result = 1;
i n t base = 2 ;
i n t exponent = 3 ;
boolean isNegative = f a l s e ;

i f ( exponent < 0 ) {
isNegative = true ;
exponent = −exponent ;
}

w h i l e ( exponent > 0 ) {
i f ( exponent % 2 == 1 ) {
r e s u l t ∗= b a s e ;
}
exponent /= 2 ;
b a s e ∗= b a s e ;
}

i f ( isNegative ) {
result = 1 / result ;
}

””
 145. Polynomial Evaluation using Horner’s
Method

Problem Description
The problem requires evaluating a polynomial for a given value of x. The polynomial is represented as an ar-
ray of coefficients, where the index of the array corresponds to the power of x. For example, the polynomial 3x2 +2x+
1wouldberepresentedas[1, 2, 3].T heinputtothealgorithmisthearrayof coef f icientsandthevalueof x, andtheoutputistheevaluatedpolyno

Example
For the polynomial
3x2 + 2x + 1, representedas[1, 2, 3], andx = 2, theexpectedoutputis3(2)2 + 2(2) + 1 = 12 + 4 + 1 = 17.

Solution
int result = 0;
int [ ] c o e f f i c i e n t s = {1 , 2 , 3};
int x = 2;
for ( i n t i = c o e f f i c i e n t s . l e n g t h − 1 ; i >= 0 ; i −−) {
result = coefficients [ i ] + x ∗ result ;
}
result = result ;

””
 146. Identity Matrix Check

Problem Description
The algorithm checks if a given square matrix is an identity matrix. An identity matrix is a square matrix with
ones on the main diagonal and zeros elsewhere. The input is a 2D array representing the matrix, and the output is
a boolean value indicating whether the matrix is an identity matrix or not.

Example
The input matrix
1 0 0
" #
0 1 0
0 0 1

should return true, while the input matrix

1 0 1
" #
0 1 0
0 0 1

should return false.

Solution
boolean i s I d e n t i t y = true ;
f o r ( i n t i = 0 ; i < matrix . l e n g t h ; i ++) {
f o r ( i n t j = 0 ; j < matrix [ 0 ] . l e n g t h ; j ++) {
i f ( i == j && matrix [ i ] [ j ] != 1 ) {
isIdentity = false ;
break ;
} e l s e i f ( i != j && matrix [ i ] [ j ] != 0 ) {
isIdentity = false ;
break ;
}
}
if (! isIdentity ) {
break ;
}
}
if ( isIdentity ) {
System . out . p r i n t l n ( ” ” t r u e ” ” ) ;
} else {
System . out . p r i n t l n ( ” ” f a l s e ” ” ) ;
}

””
 147. Transpose Matrix

Problem Description
The algorithm is designed to transpose a given matrix. The input is a 2D array of integers, and the output will be
the transposed matrix. The transpose of a matrix is obtained by swapping its rows with columns. The algorithm
will take the input matrix, swap the elements across the diagonal, and return the resulting transposed matrix.

Example
The input matrix can be:
1 2 3
" #
4 5 6
7 8 9

The expected output will be:

1 4 7
" #
2 5 8
3 6 9

Solution
int rows = matrix . l e n g t h ;
int c o l s = matrix [ 0 ] . l e n g t h ;
int [ ] [ ] t r a n s p o s e d = new i n t [ c o l s ] [ rows ] ;
for ( i n t i = 0 ; i < rows ; i ++) {
f o r ( i n t j = 0 ; j < c o l s ; j ++) {
t r a n s p o s e d [ j ] [ i ] = matrix [ i ] [ j ] ;
}
}

””
 148. Rotate Matrix 90°

Problem Description
The algorithm rotates a given matrix 90° clockwise. The input is a 2D array of integers representing the matrix, and
the output is the rotated matrix. The approach involves first transposing the matrix and then reversing each row.

Example
The input matrix is:
1 2 3
" #
4 5 6
7 8 9

The expected output is:

7 4 1
" #
8 5 2
9 6 3

Solution
i n t [ ] [ ] matrix = {
{1 , 2 , 3} ,
{4 , 5 , 6} ,
{ 7 , 8 , 9}
};
i n t n = matrix . l e n g t h ;
i n t [ ] [ ] r e s u l t = new i n t [ n ] [ n ] ;
f o r ( i n t i = 0 ; i < n ; i ++) {
f o r ( i n t j = 0 ; j < n ; j ++) {
r e s u l t [ j ] [ n − i − 1 ] = matrix [ i ] [ j ] ;
}
}
matrix = r e s u l t ;

””
 149. Rotate Matrix 180°

Problem Description
The algorithm will take a 2D matrix as input and rotate it 180°. The input matrix will be a list of lists in Java,
where each inner list represents a row in the matrix. The output will be the rotated matrix. The algorithm should
be able to handle matrices of any size.

Example
The input matrix could be: “‘ 1 2 3 4 5 6 7 8 9 “‘ The expected output would be: “‘ 9 8 7 6 5 4 3 2 1 “‘

Solution
i n t [ ] [ ] matrix = { { 1 , 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 } } ;
i n t rows = matrix . l e n g t h ;
i n t c o l s = matrix [ 0 ] . l e n g t h ;

f o r ( i n t i = 0 ; i < rows ; i ++) {

int l e f t = 0;
int right = cols − 1;
while ( l e f t < right ) {
i n t temp = matrix [ i ] [ l e f t ] ;
matrix [ i ] [ l e f t ] = matrix [ i ] [ r i g h t ] ;
matrix [ i ] [ r i g h t ] = temp ;
l e f t ++;
r i g h t −−;
}
}

f o r ( i n t i = 0 ; i < rows / 2 ; i ++) {

i n t [ ] temp = matrix [ i ] ;
matrix [ i ] = matrix [ rows − 1 − i ] ;
matrix [ rows − 1 − i ] = temp ;
}

””
 150. Find Maximum Element in Matrix

Problem Description
Find the maximum element in a given matrix. The matrix is represented as a 2D array of integers, where each inner
array has the same length. The input matrix is not empty and contains at least one row and one column. The
algorithm should return the maximum element in the matrix.
Input: A 2D array of integers Output: The maximum element in the matrix

Example
Input matrix:
1 2 3
" #
4 5 6
7 8 9

Expected output: 9

Solution
i n t maxElement = I n t e g e r . MIN VALUE ;
f o r ( i n t i = 0 ; i < matrix . l e n g t h ; i ++) {
f o r ( i n t j = 0 ; j < matrix [ i ] . l e n g t h ; j ++) {
i f ( matrix [ i ] [ j ] > maxElement ) {
maxElement = matrix [ i ] [ j ] ;
}
}
}
System . out . p r i n t l n ( maxElement ) ;

””
 151. Sum of Diagonal Elements

Problem Description
The algorithm calculates the sum of diagonal elements in a square matrix. Input: A 2D array (square matrix) of
integers. Output: The sum of the primary and secondary diagonal elements.

Example
Input:
1 2 3
" #
4 5 6
7 8 9

Output: 1 + 5 + 9 + 3 + 5 + 7 = 30

Solution
i n t sum = 0 ;
i n t s i z e = matrix . l e n g t h ;
f o r ( i n t i = 0 ; i < s i z e ; i ++) {
sum += matrix [ i ] [ i ] ;
sum += matrix [ i ] [ s i z e − i − 1 ] ;
}
i f ( s i z e % 2 == 1 ) {
sum −= matrix [ s i z e / 2 ] [ s i z e / 2 ] ;
}

””
 152. Check if Matrix is Symmetric

Problem Description
Check if a given square matrix is symmetric. A square matrix is said to be symmetric if it is equal to its transpose.
The input is a 2D array representing the matrix, and the output is a boolean value indicating whether the matrix is
symmetric or not. The matrix is represented as a list of lists, where each inner list represents a row in the matrix.

Example
Input:
1 2 3
" #
2 4 5
3 5 6

Output: true

Solution
boolean isSymmetric = true ;
i n t rows = matrix . l e n g t h ;
i n t c o l s = matrix [ 0 ] . l e n g t h ;

f o r ( i n t i = 0 ; i < rows ; i ++) {

f o r ( i n t j = 0 ; j < c o l s ; j ++) {
i f ( matrix [ i ] [ j ] != matrix [ j ] [ i ] ) {
isSymmetric = f a l s e ;
break ;
}
}
i f ( ! isSymmetric ) {
break ;
}
}
System . out . p r i n t l n ( i s S y m m e t r i c ) ;

””
 153. Spiral Order Traversal

Problem Description
The algorithm performs a spiral order traversal on a given 2D matrix. The input is a 2D array of integers, and the
output is a list of integers representing the spiral order traversal of the input matrix. The algorithm should start
from the top left corner and move right, then down, then left, and finally up, repeating this process until all
elements are visited.

Example
The input matrix is:
1 2 3
" #
4 5 6
7 8 9

The expected output is: 1 2 3 6 9 8 7 4 5

Solution
i n t rows = matrix . l e n g t h ;
i n t c o l s = matrix [ 0 ] . l e n g t h ;
i n t top = 0 ;
i n t bottom = rows − 1 ;
int l e f t = 0;
int right = cols − 1;
w h i l e ( top <= bottom && l e f t <= r i g h t ) {
f o r ( i n t i = l e f t ; i <= r i g h t ; i ++) {
r e s u l t . add ( matrix [ top ] [ i ] ) ;
}
top++;
f o r ( i n t i = top ; i <= bottom ; i ++) {
r e s u l t . add ( matrix [ i ] [ r i g h t ] ) ;
}
r i g h t −−;
i f ( top <= bottom ) {
f o r ( i n t i = r i g h t ; i >= l e f t ; i −−) {
r e s u l t . add ( matrix [ bottom ] [ i ] ) ;
}
bottom −−;
}
i f ( l e f t <= r i g h t ) {
f o r ( i n t i = bottom ; i >= top ; i −−) {
r e s u l t . add ( matrix [ i ] [ l e f t ] ) ;
}
l e f t ++;
}
}

””
 154. Zigzag Traversal

Problem Description
The zigzag traversal algorithm is used to traverse a matrix in a zigzag pattern, alternating between left-to-right and
right-to-left. The input is a 2D matrix, and the output is a list of elements in the zigzag order. The algorithm
should start from the first row and traverse the matrix row by row.

Example
For the input matrix: 1 2 3 4 5 6 7 8 9 The expected output is: 1 2 3 6 5 4 7 8 9

Solution
int rows = matrix . l e n g t h ;
int c o l s = matrix [ 0 ] . l e n g t h ;
int index = 0 ;
int [ ] r e s u l t = new i n t [ rows ∗ c o l s ] ;
for ( i n t i = 0 ; i < rows ; i ++) {
i f ( i % 2 == 0 ) {
f o r ( i n t j = 0 ; j < c o l s ; j ++) {
r e s u l t [ i n d e x++] = matrix [ i ] [ j ] ;
}
} else {
f o r ( i n t j = c o l s − 1 ; j >= 0 ; j −−) {
r e s u l t [ i n d e x++] = matrix [ i ] [ j ] ;
}
}
}

””
 155. Search Element in Sorted Matrix

Problem Description
Search for a target element in a sorted matrix. The matrix is sorted in a way that all elements in a row are sorted
in ascending order and the last element of each row is smaller than the first element of the next row. The input is a
2D matrix and a target integer, and the output is the position of the target element in the matrix if it exists,
otherwise return [-1, -1]. The matrix can be very large, so an efficient solution is required.

Example
The input matrix is:
15 20 40 85
 
20 35 80 95 
30 55 95 105
40 80 100 120

and the target element is 55. The output should be [2, 1] because 55 is at the 3rd row and 2nd column.

Solution
rows = matrix . l e n g t h
c o l s = matrix [ 0 ] . l e n g t h
row = 0
col = cols − 1

w h i l e row < rows and c o l >= 0 :

i f matrix [ row ] [ c o l ] == t a r g e t :
r e s u l t = [ row , c o l ]
break
e l i f matrix [ row ] [ c o l ] < t a r g e t :
row += 1
else :
c o l −= 1
i f row == rows o r c o l == −1:
r e s u l t = [ −1 , −1]

””
 156. Set Matrix Zeros

Problem Description
Set row and column to zero if element is zero. Given an m x n integer matrix, if an element is zero, set its entire
row and column to zero. The input is a 2D array of integers, and the output is the modified 2D array. The
algorithm should have a time complexity of O(m*n) and a space complexity of O(1) or O(m + n) if using additional
space for tracking.

Example
Input:
1 1 1
" #
1 0 1
1 1 1

Output:
1 0 1
" #
0 0 0
1 0 1

Solution
m = matrix . l e n g t h
n = matrix [ 0 ] . l e n g t h
rows = new b o o l e a n [m]
c o l s = new b o o l e a n [ n ]

f o r i i n r a n g e (m) :
f o r j in range (n) :
i f matrix [ i ] [ j ] == 0 :
rows [ i ] = t r u e
cols [ j ] = true

f o r i i n r a n g e (m) :
f o r j in range (n) :
i f rows [ i ] o r c o l s [ j ] :
matrix [ i ] [ j ] = 0

””
 157. Island Count

Problem Description
The island count problem involves counting the number of connected components (islands) in a binary matrix. The
input is a 2D binary matrix where 0 represents water and 1 represents land. The task is to count the number of
islands, where an island is defined as a group of connected land cells (horizontally or vertically). The output should
be the total count of islands in the given matrix.

Example
Consider the following binary matrix:
1 1 0 0
 
1 1 0 0
0 0 1 1
0 0 1 1

The expected output for this matrix is 2, as there are two distinct islands.

Solution
int rows = g r i d . l e n g t h ;
int cols = grid [ 0 ] . length ;
int count = 0 ;
for ( i n t i = 0 ; i < rows ; i ++) {
f o r ( i n t j = 0 ; j < c o l s ; j ++) {
i f ( g r i d [ i ] [ j ] == 1 ) {
dfs ( grid , i , j ) ;
count++;
}
}
}

void dfs ( i n t [ ] [ ] grid , i n t i , i n t j ) {

i f ( i < 0 | | j < 0 | | i >= g r i d . l e n g t h | | j >= g r i d [ 0 ] .
l e n g t h | | g r i d [ i ] [ j ] == 0 ) {
return ;
}
grid [ i ] [ j ] = 0;
dfs ( grid , i − 1 , j ) ;
dfs ( grid , i + 1 , j ) ;
d f s ( grid , i , j − 1) ;
d f s ( grid , i , j + 1) ;
}

””
 158. Path Existence in Grid (DFS)

Problem Description
The problem requires determining whether a path exists between two given points in a grid. The grid is represented
as a 2D array, where each cell can have a value of 0 (representing an empty cell) or 1 (representing a blocked cell).
The input includes the grid and the coordinates of the start and end points. The output should be a boolean value
indicating whether a path exists between the start and end points.

Example
Consider a grid with the following structure:
0 0 1
" #
0 0 0
1 0 0

Given the start point as (0, 0) and the end point as (2, 2), the output should be true, indicating that a path exists
between the start and end points.

Solution
i n t rows = g r i d . l e n g t h ;
int cols = grid [ 0 ] . length ;
b o o l e a n [ ] [ ] v i s i t e d = new b o o l e a n [ rows ] [ c o l s ] ;
i n t [ ] [ ] d i r e c t i o n s = { { 0 , 1 } , { 0 , −1} , { 1 , 0 } , { −1 , 0 } } ;

boolean dfs ( i n t x , i n t y ) {
i f ( x < 0 | | x >= rows | | y < 0 | | y >= c o l s | | g r i d [ x ] [ y ]
== 1 | | v i s i t e d [ x ] [ y ] ) {
return f a l s e ;
}
i f ( x == endX && y == endY ) {
return true ;
}
v i s i t e d [ x ] [ y ] = true ;
for ( int [ ] dir : directions ) {
i f ( dfs (x + dir [ 0 ] , y + dir [ 1 ] ) ) {
return true ;
}
}
return f a l s e ;
}

int startX = 0;
int startY = 0;
i n t endX = 2 ;
i n t endY = 2 ;
b o o l e a n r e s u l t = d f s ( startX , s t a r t Y ) ;

””
 159. Largest Rectangle in Binary Matrix

Problem Description
The problem requires finding the largest rectangle of 1s in a given binary matrix. The input is a 2D binary matrix,
and the output is the area of the largest rectangle of 1s. The matrix contains only 0s and 1s, and the rectangle must
have all its sides parallel to the sides of the matrix.

Example
Consider the following binary matrix:
1 0 1 0 0
 
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The expected output is 6, which is the area of the largest rectangle of 1s.

Solution
i n t maxRectangle = 0 ;
f o r ( i n t i = 0 ; i < matrix . l e n g t h ; i ++) {
i n t [ ] h i s t o g r a m = new i n t [ matrix [ 0 ] . l e n g t h ] ;
f o r ( i n t j = 0 ; j < matrix [ 0 ] . l e n g t h ; j ++) {
i f ( i == 0 ) {
h i s t o g r a m [ j ] = matrix [ i ] [ j ] ;
} else {
i f ( matrix [ i ] [ j ] == 1 ) {
h i s t o g r a m [ j ] += matrix [ i ] [ j ] ;
} else {
histogram [ j ] = 0 ;
}
}
}
i n t [ ] s t a c k = new i n t [ matrix [ 0 ] . l e n g t h + 1 ] ;
i n t top = −1;
i n t index = 0 ;
while ( index < histogram . length ) {
i f ( top == −1 | | h i s t o g r a m [ i n d e x ] >= h i s t o g r a m [ s t a c k [
top ] ] ) {
s t a c k [++top ] = i n d e x++;
} else {
i n t a r e a = h i s t o g r a m [ s t a c k [ top ] ] ∗ ( i n d e x − s t a c k [
top ] − 1 ) ;
i f ( i n d e x == h i s t o g r a m . l e n g t h ) {
a r e a = h i s t o g r a m [ s t a c k [ top ] ] ∗ ( i n d e x − s t a c k [
top ] ) ;
}
maxRectangle = Math . max( maxRectangle , a r e a ) ;
top −−;
 }
}
w h i l e ( top != −1) {
i n t a r e a = h i s t o g r a m [ s t a c k [ top ] ] ∗ ( h i s t o g r a m . l e n g t h −
s t a c k [ top ] ) ;
maxRectangle = Math . max( maxRectangle , a r e a ) ;
top −−;
}
}

””
 160. Count Connected Components

Problem Description
Count the number of connected components in a given grid. The grid is represented as a 2D array of integers,
where each integer is either 0 (representing an empty cell) or 1 (representing a filled cell). Two cells are considered
connected if they are adjacent (horizontally or vertically) and have the same value. The input is a 2D array of
integers, and the output is the number of connected components.

Example
Input:
1 1 0 0
 
1 1 0 0
0 0 1 1
0 0 1 1

Output: 2

Solution
d i r e c t i o n s = [ [ 0 , 1 ] , [ 0 , −1] , [ 1 , 0 ] , [ −1 , 0 ] ]
rows = g r i d . l e n g t h
cols = grid [ 0 ] . length
visited = [ [ false for in range ( c o l s ) ] f o r i n r a n g e ( rows ) ]

count = 0
f o r i i n r a n g e ( rows ) :
f o r j in range ( c o l s ) :
i f not v i s i t e d [ i ] [ j ] and g r i d [ i ] [ j ] == 1 :
count += 1
stack = [ ( i , j ) ]
v i s i t e d [ i ] [ j ] = true
while stack :
x , y = s t a c k . pop ( )
f o r dx , dy i n d i r e c t i o n s :
nx , ny = x + dx , y + dy
i f 0 <= nx < rows and 0 <= ny < c o l s and
not v i s i t e d [ nx ] [ ny ] and g r i d [ nx ] [ ny ] ==
1:
s t a c k . append ( ( nx , ny ) )
v i s i t e d [ nx ] [ ny ] = t r u e
r e t u r n count

””
 161. Word Search in Grid

Problem Description
The goal is to determine if a given word exists in a grid of characters. The word can be constructed from letters of
sequentially adjacent cell, where adjacent cells are those horizontally or vertically neighboring. The search involves
exploring all possible paths from each cell to find a match for the given word. The input consists of a 2D grid of
characters and a target word, while the output is a boolean indicating whether the word can be found in the grid.

Example
Given a grid:
A B C E
" #
S F C S
A D E E

and a word ””ABCCED””, the output should be true because the word can be formed by traversing the grid.

Solution
d i r e c t i o n s = [ [ 0 , 1 ] , [ 0 , −1] , [ 1 , 0 ] , [ −1 , 0 ] ]
rows , c o l s = g r i d . l e n g t h , g r i d [ 0 ] . l e n g t h
v i s i t e d = [ [ False for in range ( c o l s ) ] f o r i n r a n g e ( rows ) ]

d e f b a c k t r a c k ( i , j , wordIndex ) :
i f wordIndex == l e n ( word ) :
r e t u r n True
i f i < 0 o r i >= rows o r j < 0 o r j >= c o l s o r word [
wordIndex ] != g r i d [ i ] [ j ] o r v i s i t e d [ i ] [ j ] :
return False
v i s i t e d [ i ] [ j ] = True
for d in d i r e c t i o n s :
i f b a c k t r a c k ( i + d [ 0 ] , j + d [ 1 ] , wordIndex + 1 ) :
r e t u r n True
v i s i t e d [ i ] [ j ] = False
return False

f o r i i n r a n g e ( rows ) :
f o r j in range ( c o l s ) :
i f backtrack ( i , j , 0) :
r e s u l t = True
break
i f ’ r e s u l t ’ in l o c a l s () :
break

””
 162. Minimum Path Sum

Problem Description
The minimum path sum problem is a dynamic programming problem where we are given a matrix and we need to
find the minimum path sum from the top-left cell to the bottom-right cell. The path can only be constructed from
cells directly below or to the right of the current cell. The input is a 2D array of integers representing the matrix,
and the output is the minimum path sum.

Example
For the input matrix:
1 3 1
" #
1 5 1
4 2 1

The expected output is 7, which is the sum of the path: 1 (top-left) -¿ 1 (below) -¿ 1 (below) -¿ 1 (right) -¿ 3
(above-left) is not the correct path, the correct path is 1 (top-left) -¿ 3 (right) -¿ 1 (below) -¿ 1 (right).

Solution
i n t rows = matrix . l e n g t h ;
i n t c o l s = matrix [ 0 ] . l e n g t h ;
i n t [ ] [ ] dp = new i n t [ rows ] [ c o l s ] ;
dp [ 0 ] [ 0 ] = matrix [ 0 ] [ 0 ] ;
f o r ( i n t i = 1 ; i < rows ; i ++) {
dp [ i ] [ 0 ] = dp [ i − 1 ] [ 0 ] + matrix [ i ] [ 0 ] ;
}
f o r ( i n t j = 1 ; j < c o l s ; j ++) {
dp [ 0 ] [ j ] = dp [ 0 ] [ j −1] + matrix [ 0 ] [ j ] ;
}
f o r ( i n t i = 1 ; i < rows ; i ++) {
f o r ( i n t j = 1 ; j < c o l s ; j ++) {
dp [ i ] [ j ] = Math . min ( dp [ i − 1 ] [ j ] , dp [ i ] [ j −1]) + matrix [ i
][ j ];
}
}
r e t u r n dp [ rows − 1 ] [ c o l s − 1 ] ;

””
 163. Reverse Linked List

Problem Description
Reverse a singly linked list. The linked list is defined as a sequence of nodes, where each node contains a value and
a reference (i.e., ””link””) to the next node in the sequence. This sequence is considered a list because it has a
beginning (i.e., ””head””) and an end (i.e., ””tail””), and each element in the list points to the next. The input is
the head of the linked list, and the output should be the head of the reversed linked list.

Example
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Solution
ListNode prev = n u l l ;
ListNode c u r r = head ;
w h i l e ( c u r r != n u l l ) {
ListNode next = c u r r . next ;
c u r r . next = prev ;
prev = c u r r ;
c u r r = next ;
}
r e t u r n prev ;

””
 164. Find Middle of Linked List

Problem Description
Find the middle of a linked list using the slow-fast pointer approach. The input is the head of the linked list, and
the output should be the node at the middle of the list. If the list has an even number of nodes, the middle is the
second middle node. The algorithm should handle both empty and non-empty lists.

Example
Input: head = [1, 2, 3, 4, 5] Output: Node with value 3 Input: head = [1, 2, 3, 4, 5, 6] Output: Node with value 4

Solution
ListNode s l o w = head ;
ListNode f a s t = head ;
w h i l e ( f a s t != n u l l && f a s t . next != n u l l ) {
s l o w = s l o w . next ;
f a s t = f a s t . next . next ;
}
return slow ;

””
 165. Detect Cycle in Linked List

Problem Description
Detect cycle in linked list using Floyd’s cycle detection algorithm, also known as the slow and fast pointers
approach. The algorithm takes the head of a linked list as input and returns true if a cycle is present, false
otherwise. The input linked list is defined as a sequence of nodes, where each node contains an integer value and a
reference to the next node in the list.

Example
Sample input linked list: 1 -¿ 2 -¿ 3 -¿ 4 -¿ 5 -¿ 3 (cycle at node 3) Expected output: true Sample input linked list:
1 -¿ 2 -¿ 3 -¿ 4 -¿ 5 Expected output: false

Solution
s l o w = head
f a s t = head
w h i l e f a s t i s not None and f a s t . next i s not None
s l o w = s l o w . next
f a s t = f a s t . next . next
i f s l o w == f a s t
return true
return f a l s e

””
 166. Merge Two Sorted Lists

Problem Description
Merge two sorted linked lists into one sorted linked list. The input is two linked lists, and the output is a new
sorted linked list. The lists are sorted in ascending order.

Example
Input: list1 = [1, 2, 4], list2 = [1, 3, 4] Output: [1, 1, 2, 3, 4, 4] Input: list1 = [], list2 = [] Output: [] Input: list1 =
[], list2 = [0] Output: [0]

Solution
ListNode dummy = new ListNode ( 0 ) ;
ListNode c u r r e n t = dummy ;
w h i l e ( l i s t 1 != n u l l && l i s t 2 != n u l l ) {
i f ( l i s t 1 . val < l i s t 2 . val ) {
c u r r e n t . next = l i s t 1 ;
l i s t 1 = l i s t 1 . next ;
} else {
c u r r e n t . next = l i s t 2 ;
l i s t 2 = l i s t 2 . next ;
}
c u r r e n t = c u r r e n t . next ;
}
i f ( l i s t 1 != n u l l ) {
c u r r e n t . next = l i s t 1 ;
} else {
c u r r e n t . next = l i s t 2 ;
}
r e t u r n dummy . next ;

””
 167. Remove Nth Node From End

Problem Description
Remove the nth node from the end of a linked list, given the head of the list and n. The node to be removed is the
nth node from the end, and the removal should be done in one pass.
Input: head of the linked list, n Output: head of the modified linked list

Example
Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Input: head = [1], n = 1 Output: []

Solution
ListNode f i r s t = head ;
ListNode s e c o n d = head ;
f o r ( i n t i = 0 ; i < n ; i ++) {
f i r s t = f i r s t . next ;
}
i f ( f i r s t == n u l l ) {
r e t u r n head . next ;
}
w h i l e ( f i r s t . next != n u l l ) {
f i r s t = f i r s t . next ;
s e c o n d = s e c o n d . next ;
}
s e c o n d . next = s e c o n d . next . next ;
r e t u r n head ;

””
 168. Remove Duplicates from Sorted List

Problem Description
Remove duplicates from a sorted list, the list should be modified in-place. Input: A sorted list of integers. Output:
The modified list with duplicates removed. The function should return the length of the modified list.

Example
Input: 1 -¿ 1 -¿ 2 -¿ 3 -¿ 3 -¿ 4 -¿ 5 -¿ 5 Output: 1 -¿ 2 -¿ 3 -¿ 4 -¿ 5 The length of the modified list is 5.

Solution
i n t [ ] nums = new i n t [ ] { 1 , 1 , 2 , 2 , 3 , 3 , 4 , 5 , 5 } ;
int i = 0;
f o r ( i n t j = 1 ; j < nums . l e n g t h ; j ++) {
i f ( nums [ j ] != nums [ i ] ) {
i ++;
nums [ i ] = nums [ j ] ;
}
}

””
 169. Linked List Palindrome Check

Problem Description
Check if a singly linked list is a palindrome. The linked list can be empty or contain only one node. The input is
the head of the linked list, and the output is a boolean value indicating whether the linked list is a palindrome or
not. The algorithm should have a time complexity of O(n), where n is the number of nodes in the linked list, and a
space complexity of O(1), as only a constant amount of space is used.

Example
Input: 1 -¿ 2 -¿ 3 -¿ 2 -¿ 1 Output: true Input: 1 -¿ 2 -¿ 3 -¿ 4 -¿ 5 Output: false

Solution
c l a s s ListNode {
int val ;
ListNode next ;
ListNode ( i n t x ) { v a l = x ; }
}

ListNode s l o w = head ;
ListNode f a s t = head ;
w h i l e ( f a s t != n u l l && f a s t . next != n u l l ) {
s l o w = s l o w . next ;
f a s t = f a s t . next . next ;
}

ListNode s e c o n d = s l o w . next ;
s l o w . next = n u l l ;

ListNode prev = n u l l ;
w h i l e ( s e c o n d != n u l l ) {
ListNode temp = s e c o n d . next ;
s e c o n d . next = prev ;
prev = s e c o n d ;
s e c o n d = temp ;
}

ListNode f i r s t = head ;
ListNode s e c o n d H a l f = prev ;
w h i l e ( s e c o n d H a l f != n u l l ) {
i f ( f i r s t . v a l != s e c o n d H a l f . v a l ) {
return f a l s e ;
}
f i r s t = f i r s t . next ;
s e c o n d H a l f = s e c o n d H a l f . next ;
}
return true ;
””
 170. Two Pointer List Intersection

Problem Description
The problem requires finding the intersection point of two linked lists. The intersection point is where the two lists
merge into a single list. We are given the head nodes of both lists. The task is to find the intersection node and
return it. If there is no intersection, return null. The input is two linked lists, and the output is the intersection
node or null.

Example
Consider two linked lists, 4 -¿ 1 -¿ 8 -¿ 4 -¿ 5 and 5 -¿ 0 -¿ 1 -¿ 8 -¿ 4 -¿ 5. The intersection point is the node with
value 8. The expected output is the node with value 8.

Solution
i n t lengthA = 0 ;
i n t lengthB = 0 ;
currA = headA ;
currB = headB ;
w h i l e ( currA != n u l l ) {
lengthA++;
currA = currA . next ;
}
w h i l e ( currB != n u l l ) {
lengthB++;
currB = currB . next ;
}
currA = headA ;
currB = headB ;
i f ( lengthA > lengthB ) {
f o r ( i n t i = 0 ; i < lengthA − lengthB ; i ++) {
currA = currA . next ;
}
} else {
f o r ( i n t i = 0 ; i < lengthB − lengthA ; i ++) {
currB = currB . next ;
}
}
w h i l e ( currA != n u l l && currB != n u l l ) {
i f ( currA == currB ) {
r e t u r n currA ;
}
currA = currA . next ;
currB = currB . next ;
}
return null ;

””
 171. Rotate Linked List by K

Problem Description
The problem requires rotating a linked list by k positions. The linked list is defined as a sequence of nodes, where
each node contains a value and a reference to the next node. The input to the algorithm is the head of the linked
list and the number of positions k to rotate. The output is the head of the rotated linked list. The algorithm should
handle cases where k is greater than the length of the linked list.

Example
Consider a linked list with values 1 -¿ 2 -¿ 3 -¿ 4 -¿ 5 and k = 2. The rotated linked list should be 4 -¿ 5 -¿ 1 -¿ 2 -¿
3.

Solution
k = k % length of linked list
i f k == 0 :
r e t u r n head
o l d t a i l = head
f o r i in range ( l e n g t h o f l i n k e d l i s t − k − 1) :
o l d t a i l = o l d t a i l . next
n e w t a i l = o l d t a i l . next
new head = n e w t a i l
w h i l e n e w t a i l . next :
n e w t a i l = n e w t a i l . next
n e w t a i l . next = head
o l d t a i l . next = None
r e t u r n new head

””
 172. Add Two Numbers as Linked Lists

Problem Description
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse
order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. The
input of the function will be the head of the two linked lists. The output should be the head of the resulting linked
list.

Example
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Solution
ListNode dummyHead = new ListNode ( 0 ) ;
ListNode p = l 1 , q = l 2 , c u r r = dummyHead ;
int carry = 0;
w h i l e ( p != n u l l | | q != n u l l ) {
i n t x = ( p != n u l l ) ? p . v a l : 0 ;
i n t y = ( q != n u l l ) ? q . v a l : 0 ;
i n t sum = c a r r y + x + y ;
c a r r y = sum / 1 0 ;
c u r r . next = new ListNode ( sum % 1 0 ) ;
c u r r = c u r r . next ;
i f ( p != n u l l ) p = p . next ;
i f ( q != n u l l ) q = q . next ;
}
i f ( carry > 0) {
c u r r . next = new ListNode ( c a r r y ) ;
}
r e t u r n dummyHead . next ;

””
 173. Clone List with Random Pointers

Problem Description
The problem requires cloning a list with random pointers. The list is represented as a linked list where each node
has a value, a next pointer, and a random pointer. The task is to create a deep copy of the original list, including
the random pointers. The input is the head of the original list, and the output is the head of the cloned list.

Example
The input list can be represented as follows: Node 1 (value 1, next Node 2, random Node 3) Node 2 (value 2, next
Node 3, random Node 1) Node 3 (value 3, next None, random Node 2) The expected output is a cloned list with the
same structure and values, but with new nodes.

Solution
Map<Node , Node> map = new HashMap<>() ;
Node o r i g i n a l = head ;
Node newHead = n u l l ;
Node newTail = n u l l ;

w h i l e ( o r i g i n a l != n u l l ) {
Node newNode = new Node ( o r i g i n a l . v a l ) ;
map . put ( o r i g i n a l , newNode ) ;
i f ( newHead == n u l l ) {
newHead = newNode ;
newTail = newHead ;
} else {
newTail . next = newNode ;
newTail = newTail . next ;
}
o r i g i n a l = o r i g i n a l . next ;
}

o r i g i n a l = head ;
newTail = newHead ;

w h i l e ( o r i g i n a l != n u l l ) {
i f ( o r i g i n a l . random != n u l l ) {
newTail . random = map . g e t ( o r i g i n a l . random ) ;
}
o r i g i n a l = o r i g i n a l . next ;
newTail = newTail . next ;
}
r e t u r n newHead ;

””
 174. Flatten a Multilevel Linked List

Problem Description
The problem requires flattening a multilevel linked list, where each node has a value, a pointer to the next node,
and a pointer to a child node. The task is to flatten the list so that all nodes are at the same level. The input is the
head of the multilevel linked list, and the output is the head of the flattened linked list.

Example
Consider a multilevel linked list with the following structure: 1 -¿ 2 -¿ 3 -¿ 4 -¿ 5 -¿ 6 — –¿ 7 -¿ 8 -¿ 9 — –¿ 10 The
expected output after flattening is: 1 -¿ 2 -¿ 7 -¿ 8 -¿ 10 -¿ 3 -¿ 4 -¿ 5 -¿ 6 -¿ 9

Solution
Node prev = n u l l ;
Node s t a c k = head ;
w h i l e ( s t a c k != n u l l | | prev != n u l l ) {
i f ( s t a c k != n u l l ) {
prev = s t a c k ;
s t a c k = s t a c k . next ;
i f ( prev . c h i l d != n u l l ) {
Node temp = prev . c h i l d ;
prev . c h i l d = n u l l ;
Node node = s t a c k ;
w h i l e ( node != n u l l ) {
Node next = node . next ;
node . next = n u l l ;
node = next ;
}
s t a c k = temp ;
}
} else {
prev = prev . next ;
s t a c k = prev ;
}
}
r e t u r n head ;

””
 175. Balanced Parentheses Checker

Problem Description
Check if a given string of parentheses is balanced, meaning every opening parenthesis has a corresponding closing
parenthesis of the same type. The input is a string of parentheses, and the output is a boolean indicating whether
the string is balanced.

Example
Input: (()) Output: true Input: ()() Output: true Input: (())() Output: true Input: ()) Output: false

Solution
stack = [ ]
f o r char in s :
i f c h a r == ’ ( ’ o r c h a r == ’ { ’ o r c h a r == ’ [ ’ :
s t a c k . push ( c h a r )
e l i f c h a r == ’ ) ’ o r c h a r == ’ } ’ o r c h a r == ’ ] ’ :
i f s t a c k . isEmpty ( ) :
return f a l s e
top = s t a c k . pop ( )
i f ( c h a r == ’ ) ’ and top != ’ ( ’ ) o r ( c h a r == ’ } ’ and top
!= ’ { ’ ) o r ( c h a r == ’ ] ’ and top != ’ [ ’ ) :
return f a l s e
i f s t a c k . isEmpty ( ) :
return true
else :
return f a l s e

””
 176. Postfix Expression Evaluator

Problem Description
The algorithm evaluates a postfix expression using a stack data structure. The expression is given as a string array
of operands and operators. Operands are pushed onto the stack, while operators pop two operands from the stack,
perform the operation, and push the result back onto the stack. The final result is the only element left in the stack.
The input is a string array of operands and operators, and the output is the result of the evaluated expression.

Example
The input postfix expression is [””2””, ””1””, ””+””, ””3””, ””*””]. The expected output is 9. The expression is
evaluated as follows: (2 + 1) * 3 = 9.

Solution
stack = [ ]
f o r token i n t o k e n s :
i f token i n ” ”+−∗/” ” :
operand2 = s t a c k . pop ( )
operand1 = s t a c k . pop ( )
i f token == ” ”+” ” :
r e s u l t = operand1 + operand2
e l i f token == ” ”−” ” :
r e s u l t = operand1 − operand2
e l i f token == ” ” ∗ ” ” :
r e s u l t = operand1 ∗ operand2
else :
r e s u l t = i n t ( operand1 / operand2 )
s t a c k . append ( r e s u l t )
else :
s t a c k . append ( i n t ( token ) )
return stack [ 0 ]

””
 177. Infix to Postfix Conversion

Problem Description
Infix to postfix conversion is a process of converting an infix expression into a postfix expression. The infix
expression is a notation where operators are placed between operands, whereas the postfix expression is a notation
where operators are placed after operands. The input is an infix expression as a string, and the output is the
equivalent postfix expression as a string. The algorithm should handle the standard arithmetic operators (+, -, *, /)
and follow the operator precedence rules.

Example
The infix expression ””(A + B) * (C - D)”” should be converted to the postfix expression ””A B + C D - *””. The
input string can contain single-character operands (A-Z or a-z) and operators (+, -, *, /), and the output string
should be the equivalent postfix expression.

Solution
c h a r [ ] i n f i x = new c h a r [ 1 0 0 ] ;
c h a r [ ] p o s t f i x = new c h a r [ 1 0 0 ] ;
i n t top = −1;
c h a r [ ] s t a c k = new c h a r [ 1 0 0 ] ;

f o r ( i n t i = 0 ; i < i n f i x . l e n g t h ; i ++) {
i f ( i n f i x [ i ] == ’ ’ ) {
continue ;
}
i f ( i n f i x [ i ] >= ’A ’ && i n f i x [ i ] <= ’ Z ’ | | i n f i x [ i ] >= ’ a ’
&& i n f i x [ i ] <= ’ z ’ ) {
p o s t f i x [++top ] = i n f i x [ i ] ;
} e l s e i f ( i n f i x [ i ] == ’ ( ’ ) {
s t a c k [++top ] = i n f i x [ i ] ;
} e l s e i f ( i n f i x [ i ] == ’ ) ’ ) {
w h i l e ( s t a c k [ top ] != ’ ( ’ ) {
p o s t f i x [++top ] = s t a c k [ top − −];
}
top −−;
} else {
w h i l e ( top >= 0 && p r e c e d e n c e ( s t a c k [ top ] ) >= p r e c e d e n c e
( infix [ i ]) ) {
p o s t f i x [++top ] = s t a c k [ top − −];
}
s t a c k [++top ] = i n f i x [ i ] ;
}
}
w h i l e ( top >= 0 ) {
p o s t f i x [++top ] = s t a c k [ top − −];
}

””
 178. Reverse Queue using Stack

Problem Description
The problem requires reversing a given queue using a stack. The queue is defined as a First-In-First-Out (FIFO)
data structure, while the stack is a Last-In-First-Out (LIFO) data structure. The input is a queue of integers, and
the output should be the reversed queue. The algorithm should utilize the properties of stacks to reverse the order
of elements in the queue.

Example
Sample input queue: [1, 2, 3, 4, 5] Expected output queue: [5, 4, 3, 2, 1]

Solution
// I n i t i a l i z e s t a c k and queue
Stack s t a c k = new Stack ( ) ;
Queue queue = new L i n k e d L i s t ( ) ;

// Push a l l e l e m e n t s from queue t o s t a c k

w h i l e ( ! queue . isEmpty ( ) ) {
s t a c k . push ( queue . p o l l ( ) ) ;
}

// Pop a l l e l e m e n t s from s t a c k b a c k t o queue

w h i l e ( ! s t a c k . isEmpty ( ) ) {
queue . o f f e r ( s t a c k . pop ( ) ) ;
}

””
 179. Circular Queue Implementation

Problem Description
The problem requires implementing a circular queue using an array with front and rear pointers and size. The queue
should support standard operations like enqueue, dequeue, and checking if the queue is empty or full. The input
will be the queue size and the operations to be performed, and the output will be the result of these operations.

Example
The input can be the size of the queue, say 5, and the operations: enqueue(1), enqueue(2), dequeue(), enqueue(3),
enqueue(4), enqueue(5), enqueue(6). The expected output will be the result of these operations, showing the queue
state after each operation.

Solution
int front = 0;
int r e a r = −1;
int size = 0;
int queue [ ] = new i n t [ 5 ] ;

v o i d enqueue ( i n t data ) {
i f ( s i z e == queue . l e n g t h ) {
System . out . p r i n t l n ( ” ”Queue i s f u l l ” ” ) ;
return ;
}
r e a r = ( r e a r + 1 ) % queue . l e n g t h ;
queue [ r e a r ] = data ;
s i z e ++;
}

v o i d dequeue ( ) {
i f ( s i z e == 0 ) {
System . out . p r i n t l n ( ” ”Queue i s empty” ” ) ;
return ;
}
System . out . p r i n t l n ( queue [ f r o n t ] ) ;
f r o n t = ( f r o n t + 1 ) % queue . l e n g t h ;
s i z e −−;
}

v o i d printQueue ( ) {
i f ( s i z e == 0 ) {
System . out . p r i n t l n ( ” ”Queue i s empty” ” ) ;
return ;
}
i n t temp = f r o n t ;
f o r ( i n t i = 0 ; i < s i z e ; i ++) {
System . out . p r i n t ( queue [ temp ] + ” ” ” ” ) ;
 temp = ( temp + 1 ) % queue . l e n g t h ;
}
System . out . p r i n t l n ( ) ;
}

enqueue ( 1 ) ;
enqueue ( 2 ) ;
dequeue ( ) ;
enqueue ( 3 ) ;
enqueue ( 4 ) ;
enqueue ( 5 ) ;
enqueue ( 6 ) ;
printQueue ( ) ;

””
 180. Next Greater Element

Problem Description
The next greater element problem involves finding the next greater element for each element in a given array. This
means for each element, we need to find the first element to its right that is greater than it. If no such element
exists, we output -1. The input is an array of integers, and the output is an array of integers where each element at
index i represents the next greater element for the element at index i in the input array.

Example
Consider the input array [4, 5, 2, 10]. The expected output would be [5, 10, 10, -1] because: - For 4, the next
greater element is 5. - For 5, the next greater element is 10. - For 2, the next greater element is 10. - For 10, there
is no next greater element, so it’s -1.

Solution
i n t [ ] n e x t G r e a t e r E l e m e n t = new i n t [ i n p u t . l e n g t h ] ;
j a v a . u t i l . Stack<I n t e g e r > s t a c k = new j a v a . u t i l . Stack <>() ;
f o r ( i n t i = 0 ; i < i n p u t . l e n g t h ; i ++) {
w h i l e ( ! s t a c k . isEmpty ( ) && i n p u t [ s t a c k . peek ( ) ] < i n p u t [ i ] )
{
n e x t G r e a t e r E l e m e n t [ s t a c k . pop ( ) ] = i n p u t [ i ] ;
}
s t a c k . push ( i ) ;
}
w h i l e ( ! s t a c k . isEmpty ( ) ) {
n e x t G r e a t e r E l e m e n t [ s t a c k . pop ( ) ] = −1;
}

””
 181. Stock Span Problem

Problem Description
The stock span problem is a classic problem in computer science where we are given a list of stock prices for a
certain number of days, and we need to find the span of each day, which is the number of consecutive days (including
the current day) for which the stock price is less than or equal to the current day’s price. The input is an array of
integers representing the stock prices, and the output is an array of integers representing the span of each day.

Example
For example, if the input array is [10, 4, 5, 90, 120, 80], the output array would be [1, 1, 2, 4, 5, 1] because: - On
day 1, the price is 10, and there are no previous days with a higher price, so the span is 1. - On day 2, the price is
4, which is lower than the previous day, so the span is 1. - On day 3, the price is 5, which is higher than the
previous day but lower than day 1, so the span is 2. - On day 4, the price is 90, which is higher than all previous
days, so the span is 4. - On day 5, the price is 120, which is higher than all previous days, so the span is 5. - On
day 6, the price is 80, which is lower than the previous day but higher than days 1-3, so the span is 1.

Solution
i n t [ ] stockSpan ( i n t [ ] p r i c e s ) {
int n = prices . length ;
i n t [ ] span = new i n t [ n ] ;
j a v a . u t i l . Stack<I n t e g e r > s t a c k = new j a v a . u t i l . Stack <>() ;
f o r ( i n t i = 0 ; i < n ; i ++) {
w h i l e ( ! s t a c k . isEmpty ( ) && p r i c e s [ s t a c k . peek ( ) ] <=
prices [ i ]) {
s t a c k . pop ( ) ;
}
span [ i ] = s t a c k . isEmpty ( ) ? i + 1 : i − s t a c k . peek ( ) ;
s t a c k . push ( i ) ;
}
r e t u r n span ;
}

””
 182. Minimum Stack with O(1) getMin

Problem Description
Minimum stack with O(1) getMin operation can be achieved using two stacks or by storing the minimum value with
each element. The algorithm should support push, pop, and getMin operations. The input will be a series of
operations where ’push’ is followed by the value to be pushed, ’pop’ has no value, and ’getMin’ returns the current
minimum value in the stack. The output should be the result of each ’getMin’ operation.

Example
Input: push 5, push 3, push 7, getMin, pop, getMin Output: 3, 3 The input represents a series of stack operations.
The expected output is the result of each ’getMin’ operation.

Solution
i n t min = I n t e g e r .MAX VALUE;
j a v a . u t i l . Stack<I n t e g e r > s t a c k = new j a v a . u t i l . Stack <>() ;
j a v a . u t i l . Stack<I n t e g e r > minStack = new j a v a . u t i l . Stack <>() ;

v o i d push ( i n t x ) {
s t a c k . push ( x ) ;
i f ( x <= min ) {
min = x ;
minStack . push ( min ) ;
}
}

v o i d pop ( ) {
i f ( s t a c k . peek ( ) == min ) {
minStack . pop ( ) ;
i f ( ! minStack . isEmpty ( ) ) {
min = minStack . peek ( ) ;
} else {
min = I n t e g e r .MAX VALUE;
}
}
s t a c k . pop ( ) ;
}

i n t getMin ( ) {
r e t u r n min ;
}

””
 183. Interleave Queue Halves

Problem Description
Interleave the first half of a queue with the second half. The first half and second half should be determined based
on the queue’s size. If the queue has an odd size, the middle element should be considered part of the second half.
The algorithm should take a queue as input and return the interleaved queue. The input queue will contain integers.

Example
Input: [1, 2, 3, 4, 5, 6, 7] Output: [1, 4, 2, 5, 3, 6, 7] Input: [1, 2, 3, 4] Output: [1, 3, 2, 4]

Solution
Deque queue = new L i n k e d L i s t ( ) ;
Stack s t a c k = new Stack ( ) ;
i n t s i z e = queue . s i z e ( ) ;
int halfSize = size / 2;

f o r ( i n t i = 0 ; i < h a l f S i z e ; i ++) {
s t a c k . push ( queue . p o l l ( ) ) ;
}

w h i l e ( ! s t a c k . isEmpty ( ) ) {
queue . o f f e r ( s t a c k . pop ( ) ) ;
i f ( ! s t a c k . isEmpty ( ) ) {
queue . o f f e r ( s t a c k . pop ( ) ) ;
}
}

””
 184. Queue Using Stacks

Problem Description
Implement a queue using two stacks. The queue should support enqueue and dequeue operations. The input will be
a series of enqueue and dequeue operations, and the output should be the result of each dequeue operation. The
queue is empty initially.

Example
Input: enqueue(1) enqueue(2) enqueue(3) dequeue() dequeue() enqueue(4) dequeue() Output: 1 2 3

Solution
Stack enqueueStack = new Stack ( ) ;
Stack dequeueStack = new Stack ( ) ;

v o i d enqueue ( i n t x ) {
enqueueStack . push ( x ) ;
}

i n t dequeue ( ) {
i f ( dequeueStack . isEmpty ( ) ) {
w h i l e ( ! enqueueStack . isEmpty ( ) ) {
dequeueStack . push ( enqueueStack . pop ( ) ) ;
}
}
r e t u r n dequeueStack . pop ( ) ;
}

””
 185. Largest Rectangle in Histogram

Problem Description
The largest rectangle in histogram problem is a classic problem in computer science, where we are given a histogram
with different bar heights and we need to find the largest rectangle that can be formed within the histogram. The
input is an array of integers representing the heights of the bars in the histogram, and the output is the area of the
largest rectangle that can be formed. The rectangle must have its base on the x-axis and its top on one of the bars.

Example
For example, given the input [2, 1, 5, 6, 2, 3], the output should be 10, which is the area of the rectangle with
height 5 and width 2. The input matrix or data structure is a simple array of integers, and the expected output is a
single integer representing the area of the largest rectangle.

Solution
int largestRectangleArea = 0;
int [ ] h e i g h t s = new i n t [ ] { 2 , 1 , 5 , 6 , 2 , 3 } ;
int [ ] s t a c k = new i n t [ h e i g h t s . l e n g t h ] ;
int top = −1;
for ( i n t i = 0 ; i <= h e i g h t s . l e n g t h ; i ++) {
i n t h = ( i == h e i g h t s . l e n g t h ) ? 0 : h e i g h t s [ i ] ;
w h i l e ( top >= 0 && h e i g h t s [ s t a c k [ top ] ] > h ) {
i n t h e i g h t = h e i g h t s [ s t a c k [ top − −]];
i n t width = ( top >= 0 ) ? i − s t a c k [ top ] − 1 : i ;
l a r g e s t R e c t a n g l e A r e a = Math . max( l a r g e s t R e c t a n g l e A r e a ,
h e i g h t ∗ width ) ;
}
s t a c k [++top ] = i ;
}

””
 186. Longest Common Subsequence

Problem Description
The longest common subsequence problem is a classic problem in computer science and operations research that
involves finding the longest sequence that appears in the same order in two or more sequences. Given two
sequences, find the length of their longest common subsequence. The input consists of two strings, and the output
is the length of their longest common subsequence.

Example
For example, given two strings ””AGGTAB”” and ””GXTXAYB””, the longest common subsequence is ””GTAB””
with a length of 4.

Solution
int m = 0 , n = 0;
S t r i n g s 1 = ” ”AGGTAB” ” ;
S t r i n g s 2 = ” ”GXTXAYB” ” ;
m = s1 . length ( ) ;
n = s2 . length ( ) ;
i n t [ ] [ ] dp = new i n t [m + 1 ] [ n + 1 ] ;
f o r ( i n t i = 0 ; i <= m; i ++) {
f o r ( i n t j = 0 ; j <= n ; j ++) {
i f ( i == 0 | | j == 0 ) {
dp [ i ] [ j ] = 0 ;
} e l s e i f ( s 1 . charAt ( i − 1 ) == s 2 . charAt ( j − 1 ) ) {
dp [ i ] [ j ] = dp [ i − 1 ] [ j − 1 ] + 1 ;
} else {
dp [ i ] [ j ] = Math . max( dp [ i − 1 ] [ j ] , dp [ i ] [ j − 1 ] ) ;
}
}
}
i n t r e s u l t = dp [m] [ n ] ;

””
 187. Longest Common Substring

Problem Description
The longest common substring problem is a classic problem in computer science and coding interviews. Given two
strings, find the length of their longest common substring. A substring is a contiguous sequence of characters within
a string. The input consists of two strings, and the output is the length of their longest common substring. The
goal is to develop an efficient algorithm to solve this problem using dynamic programming with a continuous
matching requirement.

Example
Consider two input strings: ””abcdabc”” and ””abcabc””. The longest common substring is ””abcabc”” with a
length of 6. Another example is the input strings ””abcdef”” and ””zbcdfg””, where the longest common substring
is ””bcd”” with a length of 3.

Solution
i n t [ ] [ ] dp = new i n t [ s t r 1 . l e n g t h ( ) + 1 ] [ s t r 2 . l e n g t h ( ) + 1 ] ;
i n t maxLength = 0 ;
f o r ( i n t i = 1 ; i <= s t r 1 . l e n g t h ( ) ; i ++) {
f o r ( i n t j = 1 ; j <= s t r 2 . l e n g t h ( ) ; j ++) {
i f ( s t r 1 . charAt ( i − 1 ) == s t r 2 . charAt ( j − 1 ) ) {
dp [ i ] [ j ] = dp [ i − 1 ] [ j − 1 ] + 1 ;
maxLength = Math . max( maxLength , dp [ i ] [ j ] ) ;
} else {
dp [ i ] [ j ] = 0 ;
}
}
}
r e t u r n maxLength ;

””
 188. Minimum Jumps to Reach End

Problem Description
The minimum jumps to reach end problem is a classic problem in algorithm design. Given an array of non-negative
integers, you are initially positioned at the first index of the array. Each element in the array represents your
maximum jump length at that position. Determine the minimum number of jumps required to reach the last index.
The input is an array of integers, and the output is the minimum number of jumps.

Example
For example, given the array [2,3,1,1,4], the minimum number of jumps to reach the end is 2. You can jump from
index 0 to index 1, then from index 1 to index 4.

Solution
int jumps = 0 ;
int currEnd = 0 ;
int farthest = 0;
for ( i n t i = 0 ; i < a r r . l e n g t h − 1 ; i ++) {
f a r t h e s t = Math . max( f a r t h e s t , i + a r r [ i ] ) ;
i f ( i == currEnd ) {
jumps++;
currEnd = f a r t h e s t ;
}
}
r e t u r n jumps ;

””
 189. Coin Change

Problem Description
The coin change problem is a classic dynamic programming problem where we are given a set of coins with different
denominations and a total amount of money. The goal is to find the minimum number of coins needed to make up
the given amount using the available coins. The input consists of an array of coin denominations and the total
amount, and the output is the minimum number of coins required. If it’s not possible to make up the amount, the
output should be -1.

Example
For example, given the coin denominations [1, 2, 5] and the total amount 11, the minimum number of coins needed
is 3 (5 + 5 + 1). If the coin denominations are [2] and the total amount is 3, the output should be -1 because it’s
not possible to make up the amount with the available coins.

Solution
int [ ] c o i n s = {1 , 2 , 5};
int amount = 1 1 ;
int [ ] dp = new i n t [ amount + 1 ] ;
for ( i n t i = 0 ; i <= amount ; i ++) {
dp [ i ] = I n t e g e r .MAX VALUE;
}
dp [ 0 ] = 0 ;
f o r ( i n t i = 1 ; i <= amount ; i ++) {
for ( int coin : coins ) {
i f ( i >= c o i n && dp [ i − c o i n ] != I n t e g e r .MAX VALUE) {
dp [ i ] = Math . min ( dp [ i ] , dp [ i − c o i n ] + 1 ) ;
}
}
}
i f ( dp [ amount ] == I n t e g e r .MAX VALUE) {
r e t u r n −1;
} else {
r e t u r n dp [ amount ] ;
}

””
 190. Maximum Sum of Non-Adjacent
Elements

Problem Description
The problem requires finding the maximum sum of non-adjacent elements in an array. Given a list of integers, the
task is to determine the maximum sum that can be obtained by selecting non-adjacent elements. The input is an
array of integers, and the output is the maximum sum of non-adjacent elements.

Example
For the input array [2, 7, 9, 3, 1], the expected output is 12, which can be obtained by selecting the elements 2, 9,
and 1. For the input array [5, 1, 1, 5], the expected output is 10, which can be obtained by selecting the elements 5
and 5.

Solution
i n t maxSum = 0 ;
i f ( nums . l e n g t h == 0 ) {
maxSum = 0 ;
} e l s e i f ( nums . l e n g t h == 1 ) {
maxSum = nums [ 0 ] ;
} e l s e i f ( nums . l e n g t h == 2 ) {
maxSum = Math . max( nums [ 0 ] , nums [ 1 ] ) ;
} else {
i n t [ ] dp = new i n t [ nums . l e n g t h ] ;
dp [ 0 ] = nums [ 0 ] ;
dp [ 1 ] = Math . max( nums [ 0 ] , nums [ 1 ] ) ;
f o r ( i n t i = 2 ; i < nums . l e n g t h ; i ++) {
dp [ i ] = Math . max( dp [ i −1] , dp [ i −2] + nums [ i ] ) ;
}
maxSum = dp [ nums . l e n g t h − 1 ] ;
}

””
191. Palindrome Partitioning Minimum Cuts

Problem Description
The problem requires finding the minimum number of cuts needed to partition a given string into all possible
palindromic substrings. Given a string s, partition s into all possible palindrome partitions and return the minimum
number of cuts. The input is a string s, and the output is the minimum number of cuts required to make all
substrings palindromes.

Example
For example, given the string ””aab””, the minimum cuts would be 1, as we can partition it into ””aa”” and ””b””,
both of which are palindromes. Another example would be the string ””abc””, which would require 2 cuts to
partition it into ””a””, ””b””, and ””c””, all of which are palindromes.

Solution
b o o l e a n [ ] [ ] i s P a l i n d r o m e = new b o o l e a n [ s . l e n g t h ( ) ] [ s . l e n g t h ( ) ] ;
i n t [ ] dp = new i n t [ s . l e n g t h ( ) ] ;

f o r ( i n t i = 0 ; i < s . l e n g t h ( ) ; i ++) {
isPalindrome [ i ] [ i ] = true ;
dp [ i ] = i ;
}
f o r ( i n t i = 0 ; i < s . l e n g t h ( ) − 1 ; i ++) {
i f ( s . charAt ( i ) == s . charAt ( i + 1 ) ) {
isPalindrome [ i ] [ i + 1] = true ;
}
}
f o r ( i n t l e n g t h = 3 ; l e n g t h <= s . l e n g t h ( ) ; l e n g t h++) {
f o r ( i n t i = 0 ; i <= s . l e n g t h ( ) − l e n g t h ; i ++) {
int j = i + length − 1;
i f ( s . charAt ( i ) == s . charAt ( j ) && i s P a l i n d r o m e [ i + 1 ] [ j
− 1]) {
isPalindrome [ i ] [ j ] = true ;
}
}
}
f o r ( i n t i = 1 ; i < s . l e n g t h ( ) ; i ++) {
i f ( isPalindrome [ 0 ] [ i ] ) {
dp [ i ] = 0 ;
} else {
f o r ( i n t j = 0 ; j < i ; j ++) {
i f ( i s P a l i n d r o m e [ j + 1 ] [ i ] && dp [ j ] + 1 < dp [ i ] ) {
dp [ i ] = dp [ j ] + 1 ;
}
}
}
}
r e t u r n dp [ s . l e n g t h ( ) − 1 ] ;
””
 192. Single Number

Problem Description
The problem requires finding a unique element in an array where all other elements appear twice. The input is an
array of integers, and the output is the unique element. The algorithm should have a time complexity of O(n) and a
space complexity of O(1).

Example
The input array is [2, 2, 1], and the expected output is 1. Another example is [4, 1, 2, 1, 2], and the expected
output is 4.

Solution
i n t singleNumber = 0 ;
f o r ( i n t num : nums ) {
singleNumber ˆ= num ;
}
r e t u r n singleNumber ;

””
 193. Find Two Unique Elements

Problem Description
The problem requires finding two unique elements in an array where every element appears twice except two
elements. The input is an array of integers and the output should be the two unique elements. The array can
contain duplicate elements and the unique elements can be any integer.

Example
The input array can be [1, 2, 1, 3, 4, 4, 2] and the expected output is [3, 1] or [1, 3]. Another example can be [2, 2,
1, 3, 1, 4, 4, 5, 6, 6] and the expected output is [3, 5] or [5, 3].

Solution
i n t xor = 0 ;
f o r ( i n t num : nums ) {
xor ˆ= num ;
}
i n t r i g h t m o s t s e t b i t = xor & −xor ;
i n t unique1 = 0 , unique2 = 0 ;
f o r ( i n t num : nums ) {
i f ( ( num & r i g h t m o s t s e t b i t ) != 0 ) {
unique1 ˆ= num ;
} else {
unique2 ˆ= num ;
}
}
System . out . p r i n t l n ( unique1 + ” ” ” ” + unique2 ) ;

””
194. Find Element Where All Others Appear
Thrice

Problem Description
Find the element that appears only once in the array where every other element appears exactly three times. The
input is an array of integers and the output should be the single number that appears once. The array will contain
at least one element and a maximum of 10000 elements. Each element will be between 1 and 10000.

Example
Input: nums = [2,2,3,2] Output: 3 Explanation: Because 2 appears three times, but 3 appears only once.

Solution
i n t singleNumber = 0 ;
f o r ( i n t i = 0 ; i < 3 2 ; i ++) {
i n t count = 0 ;
f o r ( i n t num : nums ) {
count += (num >> i ) & 1 ;
}
singleNumber |= ( count % 3 ) << i ;
}

””
 195. Count Set Bits in Integer

Problem Description
Count the number of set bits in a given integer. The input is a 32-bit signed integer and the output should be the
number of set bits in the binary representation of the integer.

Example
Input: n = 9 (binary: 1001) Output: 2 Explanation: The binary representation of 9 has 2 set bits.

Solution
int countSetBits = 0;
i n t n = 9 ; // i n p u t i n t e g e r
w h i l e ( n != 0 ) {
n = n & (n − 1) ;
c o u n t S e t B i t s ++;
}
System . out . p r i n t l n ( c o u n t S e t B i t s ) ;

””
 196. Generate Subsets using Bitmasks

Problem Description
Generate all subsets of a given set using bitmasks. The input is a set of integers, and the output is all possible
subsets of the given set. The algorithm should use the binary representation of numbers to generate the subsets.

Example
Input: [1, 2, 3] Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Solution
i n t n = nums . l e n g t h ;
f o r ( i n t i = 0 ; i < ( 1 << n ) ; i ++) {
subset = [ ] ;
f o r ( i n t j = 0 ; j < n ; j ++) {
i f ( ( i & ( 1 << j ) ) != 0 ) {
s u b s e t . add ( nums [ j ] ) ;
}
}
s u b s e t s . add ( s u b s e t ) ;
}

””
 197. BFS Traversal of Graph

Problem Description
Breadth-First Search (BFS) traversal of a graph is a technique used to visit all the nodes in the graph level by level,
starting from a given source node. The algorithm uses a queue data structure to keep track of the nodes to be
visited. The input to the algorithm is an adjacency list representation of the graph and the source node. The
output is the order in which the nodes are visited.

Example
Consider a graph with the following adjacency list representation: 0 -¿ 1, 2 1 -¿ 3, 4 2 -¿ 5 3 -¿ 6 4 -¿ 7 5 -¿ 8 6 -¿ 7
-¿ 8 -¿ The BFS traversal of this graph starting from node 0 would be: 0, 1, 2, 3, 4, 5, 6, 7, 8.

Solution
i n t [ ] v i s i t e d = new i n t [ n ] ;
Queue<I n t e g e r > queue = new L i n k e d L i s t <>() ;
queue . add ( s o u r c e ) ;
v i s i t e d [ source ] = 1;
w h i l e ( ! queue . isEmpty ( ) ) {
i n t node = queue . p o l l ( ) ;
System . out . p r i n t ( node + ” ” ” ” ) ;
f o r ( i n t n e i g h b o r : a d j a c e n c y L i s t [ node ] ) {
i f ( v i s i t e d [ n e i g h b o r ] == 0 ) {
queue . add ( n e i g h b o r ) ;
v i s i t e d [ neighbor ] = 1;
}
}
}

””
 198. Depth-First Search Traversal

Problem Description
Depth-First Search (DFS) is a traversal approach in which the leftmost branch is explored as far as possible before
moving to the right. The algorithm starts at the root node, explores as far as possible along each branch before
backtracking. The input to the algorithm is an adjacency list or matrix representation of a graph, and the output is
the order of visited nodes.

Example
Consider a sample graph with nodes 0-4 and the following adjacency list: 0 -¿ 1, 2 1 -¿ 3 2 -¿ 4 The expected output
of a DFS traversal starting from node 0 could be: 0, 1, 3, 2, 4

Solution
b o o l e a n [ ] v i s i t e d = new b o o l e a n [ n ] ;
Stack<I n t e g e r > s t a c k = new Stack <>() ;
s t a c k . push ( 0 ) ;
w h i l e ( ! s t a c k . isEmpty ( ) ) {
i n t node = s t a c k . pop ( ) ;
i f ( ! v i s i t e d [ node ] ) {
v i s i t e d [ node ] = t r u e ;
System . out . p r i n t ( node + ” ” ” ” ) ;
f o r ( i n t n e i g h b o r : a d j a c e n c y L i s t [ node ] ) {
i f ( ! v i s i t e d [ neighbor ] ) {
s t a c k . push ( n e i g h b o r ) ;
}
}
}
}

””
 199. Binary Tree Level Order Traversal

Problem Description
The problem requires performing a level order traversal of a binary tree. Given the root of a binary tree, return the
level order traversal of its nodes’ values. The input is the root of the binary tree, and the output is a 2D list where
each sublist contains the node values at a given level.

Example
For the given binary tree: 3 / 9 20 / 15 7 The expected output is: [ [3], [9, 20], [15, 7] ]

Solution
Queue<Node> queue = new L i n k e d L i s t <>() ;
queue . o f f e r ( r o o t ) ;
L i s t <L i s t <I n t e g e r >> r e s u l t = new A r r a y L i s t <>() ;
w h i l e ( ! queue . isEmpty ( ) ) {
i n t l e v e l S i z e = queue . s i z e ( ) ;
L i s t <I n t e g e r > l e v e l N o d e s = new A r r a y L i s t <>() ;
f o r ( i n t i = 0 ; i < l e v e l S i z e ; i ++) {
Node currentNode = queue . p o l l ( ) ;
l e v e l N o d e s . add ( currentNode . v a l ) ;
i f ( currentNode . l e f t != n u l l ) {
queue . o f f e r ( currentNode . l e f t ) ;
}
i f ( currentNode . r i g h t != n u l l ) {
queue . o f f e r ( currentNode . r i g h t ) ;
}
}
r e s u l t . add ( l e v e l N o d e s ) ;
}
return r e s u l t ;

””
 200. Detect Cycle in Undirected Graph

Problem Description
Detect whether a cycle exists in an undirected graph. The graph is represented as an adjacency list where each
index represents a node and its corresponding value is a list of neighboring nodes. The input is the adjacency list
representation of the graph and the output is a boolean indicating whether a cycle exists in the graph.

Example
Input: adjacency list representation of the graph: [[1, 2], [0, 2], [0, 1, 3], [2]] Output: true Input: adjacency list
representation of the graph: [[1, 2], [0, 2], [0, 1]] Output: true Input: adjacency list representation of the graph: [[1],
[0, 2], [1]] Output: false

Solution
b o o l e a n [ ] v i s i t e d = new b o o l e a n [ graph . l e n g t h ] ;
boolean c y c l e = f a l s e ;
f o r ( i n t i = 0 ; i < graph . l e n g t h ; i ++) {
if (! visited [ i ]) {
c y c l e = d f s ( graph , i , −1, v i s i t e d ) ;
i f ( c y c l e ) break ;
}
}
return cycle ;

b o o l e a n d f s ( i n t [ ] [ ] graph , i n t node , i n t parent , b o o l e a n [ ]

visited ) {
v i s i t e d [ node ] = t r u e ;
f o r ( i n t n e i g h b o r : graph [ node ] ) {
i f ( ! v i s i t e d [ neighbor ] ) {
i f ( d f s ( graph , n e i g h b o r , node , v i s i t e d ) ) r e t u r n
true ;
} e l s e i f ( n e i g h b o r != p a r e n t ) {
return true ;
}
}
return f a l s e ;
}

””
 201. Shortest Path in Unweighted Graph

Problem Description
The problem requires finding the shortest path between a source and destination node in an unweighted graph. The
graph is represented as an adjacency list. The input consists of the graph, source node, and destination node. The
output should be the shortest path from the source to the destination node. If no path exists, the output should
indicate that.

Example
Consider an unweighted graph with the following adjacency list: (0 -¿ 1, 2), (1 -¿ 0, 3), (2 -¿ 0, 4), (3 -¿ 1), (4 -¿ 2).
For a source node 0 and destination node 3, the expected output is: 0 1 3.

Solution
queue = [ ]
visited = []
path = [ ]

source = 0
destination = 3

queue . append ( s o u r c e )
v i s i t e d . append ( s o u r c e )
path . append ( [ s o u r c e ] )

w h i l e queue :
node = queue . pop ( 0 )
path node = path . pop ( 0 )

i f node == d e s t i n a t i o n :
p r i n t ( path node )
break

f o r n e i g h b o r i n graph [ node ] :
i f n e i g h b o r not i n v i s i t e d :
queue . append ( n e i g h b o r )
v i s i t e d . append ( n e i g h b o r )
path . append ( path node + [ n e i g h b o r ] )