○​

@the_dev_xplained
THE ULTIMATE CODING CHEAT SHEET
Follow us on Instagram

@the_DevXplained @the_dev_xplained
 ○​

Coding Problems with Solution

Mathematical problems:

1.​ Swap two numbers without using temporary variable

What is XOR (^) ?

●​ XOR stands for "exclusive OR".

●​ It follows these rules:
○​ Same bits → 0
○​ Different bits → 1

Example:​
5 = 0101
3 = 0011
5 ^ 3 = 0110 (6)

XOR Swap Algorithm (Step-by-Step)

1.​ First XOR Operation:​

○​ a = a ^ b
○​ Stores XOR result in a.
○​ Example: 5 ^ 3 = 6, so now a = 6 and b = 3.
2.​ Second XOR Operation:​

○​ b = a ^ b
○​ Restores b to original a.
○​ Example: 6 ^ 3 = 5, so now b = 5 and a = 6.
3.​ Third XOR Operation:​

○​ a = a ^ b
○​ Restores a to original b.

@the_DevXplained @the_dev_xplained
 ○​

○​ Example: 6 ^ 5 = 3, so now a = 3 and b = 5.

Final Result

●​ Original: a = 5, b = 3
●​ After Swap: a = 3, b = 5

Code Implementation

Python
def xor_swap(a, b):
a=a^b
b=a^b
a=a^b
return a, b

# Example usage
a, b = 5, 3
print("Before Swap: a =", a, ", b =", b)
a, b = xor_swap(a, b)
print("After Swap: a =", a, ", b =", b)

C++
#include <iostream>
using namespace std;

void xorSwap(int &a, int &b) {

a = a ^ b;
b = a ^ b;
a = a ^ b;
}

int main() {
int a = 5, b = 3;
cout << "Before Swap: a = " << a << ", b = " << b << endl;
xorSwap(a, b);
cout << "After Swap: a = " << a << ", b = " << b << endl;
return 0;

@the_DevXplained @the_dev_xplained
 ○​

Java
public class XorSwap {
public static void xorSwap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
[Link]("After Swap: a = " + a + ", b = " + b);
}

public static void main(String[] args) {

int a = 5, b = 3;
[Link]("Before Swap: a = " + a + ", b = " + b);
xorSwap(a, b);
}
}

Key XOR Properties Used:

●​ x ^ x = 0
●​ x ^ 0 = x
●​ x ^ y ^ x = y (since x ^ x = 0, it cancels out)

2. Check if a number is even or odd without using modulo (%)

Algorithm: To determine whether a number is even or odd without using the modulo (%)
operator, we can utilize bitwise operations or arithmetic properties:

1.​ Using Bitwise AND Operator (&):​

○​ The least significant bit (LSB) of an even number is always 0 (e.g., 4 -> 100, 6
-> 110).
○​ The LSB of an odd number is always 1 (e.g., 3 -> 011, 5 -> 101).
○​ Performing num & 1 checks if the LSB is 1 (odd) or 0 (even).
2.​ Using Division and Multiplication:​

○​ Compute num / 2 and store the result as an integer.

○​ Multiply this result back by 2.

@the_DevXplained @the_dev_xplained
 ○​

○​ If the result equals the original number, it is even; otherwise, it is odd.

Code Implementation

Python:

# Using Bitwise AND

def is_even(n):
return (n & 1) == 0

# Using Division and Multiplication

def is_even_alt(n):
return (n // 2) * 2 == n

# Example Usage
num = int(input("Enter a number: "))
print("Even" if is_even(num) else "Odd")

C++:

#include <iostream>
using namespace std;

// Using Bitwise AND

bool isEven(int n) {
return (n & 1) == 0;
}

// Using Division and Multiplication

bool isEvenAlt(int n) {
return (n / 2) * 2 == n;
}

int main() {
int num;
cout << "Enter a number: ";
cin >> num;
cout << (isEven(num) ? "Even" : "Odd") << endl;
return 0;
}

@the_DevXplained @the_dev_xplained
 ○​

Java:

import [Link];

public class EvenOddCheck {

// Using Bitwise AND
static boolean isEven(int n) {
return (n & 1) == 0;
}

// Using Division and Multiplication

static boolean isEvenAlt(int n) {
return (n / 2) * 2 == n;
}

public static void main(String[] args) {

Scanner scanner = new Scanner([Link]);
[Link]("Enter a number: ");
int num = [Link]();
[Link]();

[Link](isEven(num) ? "Even" : "Odd");

}
}

3. Find if a number is a power of 2

Algorithm Explanation

A number is a power of 2 if it has exactly one bit set in its binary representation. This means that
for a number n, it should satisfy the condition:

n & (n - 1) == 0

Steps to check if a number is a power of 2:

1.​ If n is less than or equal to 0, return False (since negative numbers and zero are not
powers of 2).
2.​ Perform the bitwise AND operation n & (n - 1). If the result is 0, then n is a power of
2; otherwise, it is not.

@the_DevXplained @the_dev_xplained
 ○​

Python
def is_power_of_two(n):
if n <= 0:
return False
return (n & (n - 1)) == 0

# Example usage:
n = 16
print(is_power_of_two(n)) # Output: True

C++
#include <iostream>
using namespace std;

bool isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}

int main() {
int n = 16;
cout << (isPowerOfTwo(n) ? "True" : "False") << endl; // Output: True
return 0;
}

Java
public class PowerOfTwoCheck {
public static boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}

public static void main(String[] args) {

int n = 16;
[Link](isPowerOfTwo(n)); // Output: True
}
}

@the_DevXplained @the_dev_xplained
 ○​

4. Calculate the greatest common divisor (GCD) - Euclidean Algorithm

Algorithm Explanation

The Euclidean algorithm is an efficient method for computing the Greatest Common Divisor
(GCD) of two numbers. The GCD of two integers is the largest number that divides both of them
without leaving a remainder.

Steps to Calculate GCD using Euclidean Algorithm:

1.​ If b is 0, return a as the GCD.

2.​ Otherwise, replace a with b and b with a % b.
3.​ Repeat the process until b becomes 0.
4.​ The final value of a is the GCD.

Python:
def gcd(a, b):
while b:
a, b = b, a % b
return a

# Example usage:
print(gcd(48, 18)) # Output: 6

C++:
#include <iostream>
using namespace std;

int gcd(int a, int b) {

while (b) {
int temp = b;
b = a % b;
a = temp;
}
return a;

@the_DevXplained @the_dev_xplained
 ○​

int main() {
cout << gcd(48, 18) << endl; // Output: 6
return 0;
}

Java:
public class GCD {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

public static void main(String[] args) {

[Link](gcd(48, 18)); // Output: 6
}
}

5. Check if a number is a prime number

Algorithm:

A prime number is a number greater than 1 that has no divisors other than 1 and itself. To check
if a number n is prime:

Steps to Check if a Number is Prime:

1.​ If n is less than or equal to 1, return False (since prime numbers start from 2).
2.​ If n is 2 or 3, return True (since they are the smallest prime numbers).
3.​ If n is even or divisible by 3, return False.
4.​ Check divisibility from 5 to sqrt(n) with increments of 6 (i and i+2) since all primes
greater than 3 are of the form 6k ± 1.
5.​ If no divisors are found, return True.

@the_DevXplained @the_dev_xplained
 ○​

Python
import math

def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False

i=5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6

return True

# Example usage:
print(is_prime(29)) # Output: True

C++
#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;

for (int i = 5; i * i <= n; i += 6) {

if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}

@the_DevXplained @the_dev_xplained
 ○​

int main() {
cout << (isPrime(29) ? "True" : "False") << endl; // Output: True
return 0;
}

Java
public class PrimeCheck {
public static boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;

for (int i = 5; i * i <= n; i += 6) {

if (n % i == 0 || n % (i + 2) == 0) return false;
}
return true;
}

public static void main(String[] args) {

[Link](isPrime(29)); // Output: True
}
}

String Problems:
1.​ Reverse a string

Algorithm Explanation

Reversing a string means rearranging its characters in the opposite order. The following
approaches can be used:

Steps to Reverse a String:

1.​ Iterative Approach: Use a loop to swap characters from both ends moving toward the
center.
2.​ Using Built-in Functions: Many languages provide built-in functions to reverse a string
efficiently.

@the_DevXplained @the_dev_xplained
 ○​

3.​ Using Recursion: Recursively reverse the substring excluding the first character and
append the first character at the end.

Python:
def reverse_string(s):
return s[::-1] # Using slicing

# Example usage:
print(reverse_string("hello")) # Output: "olleh"

C++:
#include <iostream>
#include <algorithm>
using namespace std;

string reverseString(string s) {
reverse([Link](), [Link]());
return s;
}

int main() {
cout << reverseString("hello") << endl; // Output: "olleh"
return 0;
}

Java:
public class ReverseString {
public static String reverseString(String s) {
return new StringBuilder(s).reverse().toString();
}

public static void main(String[] args) {

[Link](reverseString("hello")); // Output: "olleh"
}
}

2. Check if a string is a palindrome:

Algorithm:

@the_DevXplained @the_dev_xplained
 ○​

A palindrome is a string that reads the same forward and backward. To check if a string is a
palindrome efficiently, we use the Two-Pointer Approach, which avoids extra space usage for
reversing the string.

Two-Pointer Approach:

1.​ Use two pointers: one at the beginning (left) and one at the end (right) of the string.
2.​ Compare the characters at both positions.
3.​ If they match, move left forward and right backward.
4.​ If any mismatch is found, return False (not a palindrome).
5.​ Continue until the pointers meet or cross each other.

This approach runs in O(N) time complexity and uses O(1) extra space.

Python:
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

# Example usage:
print(is_palindrome("racecar")) # Output: True

C++:
#include <iostream>
using namespace std;

bool isPalindrome(string s) {
int left = 0, right = [Link]() - 1;
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}

@the_DevXplained @the_dev_xplained
 ○​

int main() {
cout << (isPalindrome("racecar") ? "True" : "False") << endl; // Output: True
return 0;
}

Java:
public class PalindromeCheck {
public static boolean isPalindrome(String s) {
int left = 0, right = [Link]() - 1;
while (left < right) {
if ([Link](left) != [Link](right)) {
return false;
}
left++;
right--;
}
return true;
}

public static void main(String[] args) {

[Link](isPalindrome("racecar")); // Output: True
}
}

3. Count the occurrence of a character in a string:

Algorithm:

To count the occurrences of a character in a string, we can use different approaches:

Iterative Approach:

1.​ Initialize a counter variable to zero.

2.​ Iterate through each character of the string.
3.​ If the character matches the target character, increment the counter.
4.​ Return the final count.

This approach runs in O(N) time complexity and uses O(1) extra space.

Python:

@the_DevXplained @the_dev_xplained
 ○​

def count_char(s, c):

count = 0
for char in s:
if char == c:
count += 1
return count

# Example usage:
print(count_char("hello", 'l')) # Output: 2

C++:
#include <iostream>
using namespace std;

int countChar(string s, char c) {

int count = 0;
for (char ch : s) {
if (ch == c) count++;
}
return count;
}

int main() {
cout << countChar("hello", 'l') << endl; // Output: 2
return 0;
}

Java:
public class CharacterCount {
public static int countChar(String s, char c) {
int count = 0;
for (char ch : [Link]()) {
if (ch == c) count++;
}
return count;
}

public static void main(String[] args) {

[Link](countChar("hello", 'l')); // Output: 2

@the_DevXplained @the_dev_xplained
 ○​

}
}

4. Check if one string is an anagram of another

Algorithm Explanation

An anagram is a word or phrase formed by rearranging the letters of another. The most efficient
way to check if two strings are anagrams is the Frequency Count Approach.

Frequency Count Approach:

1.​ If the lengths of both strings are different, they cannot be anagrams.
2.​ Use an array (or hashmap) to count the occurrences of each character in the first string.
3.​ Decrease the count for each character in the second string.
4.​ If all counts return to zero, the strings are anagrams.

Time Complexity: O(N) (since we traverse both strings once) Space Complexity: O(1) (since the
character count array has a fixed size of 26 for lowercase letters or 256 for extended ASCII)

Python:
def is_anagram(s1, s2):
if len(s1) != len(s2):
return False

count = [0] * 256

for c1, c2 in zip(s1, s2):
count[ord(c1)] += 1
count[ord(c2)] -= 1

return all(x == 0 for x in count)

# Example usage:
print(is_anagram("listen", "silent")) # Output: True

C++:
#include <iostream>
using namespace std;

@the_DevXplained @the_dev_xplained
 ○​

bool isAnagram(string s1, string s2) {

if ([Link]() != [Link]()) return false;

int count[256] = {0};

for (int i = 0; i < [Link](); i++) {
count[s1[i]]++;
count[s2[i]]--;
}

for (int i = 0; i < 256; i++) {

if (count[i] != 0) return false;
}
return true;
}

int main() {
cout << (isAnagram("listen", "silent") ? "True" : "False") << endl; // Output: True
return 0;
}

Java:
public class AnagramCheck {
public static boolean isAnagram(String s1, String s2) {
if ([Link]() != [Link]()) return false;

int[] count = new int[256];

for (int i = 0; i < [Link](); i++) {
count[[Link](i)]++;
count[[Link](i)]--;
}

for (int num : count) {

if (num != 0) return false;
}
return true;
}

public static void main(String[] args) {

[Link](isAnagram("listen", "silent")); // Output: True
}

@the_DevXplained @the_dev_xplained
 ○​

}
5. Find the first repeated character in a string:

Algorithm

To find the first repeated character in a string efficiently, we use the Hash Set Approach.

Hash Set Approach:

1.​ Initialize an empty hash set.

2.​ Iterate through each character in the string.
3.​ If the character is already in the set, return it as the first repeated character.
4.​ Otherwise, add the character to the set.
5.​ If no character repeats, return a special indicator (e.g., None or -1).

Time Complexity: O(N) (since we traverse the string once) Space Complexity: O(N) (in the worst
case, we store all unique characters)

Python:
def first_repeated_char(s):
seen = set()
for char in s:
if char in seen:
return char
[Link](char)
return None # No repeated character found

# Example usage:
print(first_repeated_char("abca")) # Output: 'a'

C++:
#include <iostream>
#include <unordered_set>
using namespace std;

char firstRepeatedChar(const string &s) {

unordered_set<char> seen;
for (char c : s) {
if ([Link](c) != [Link]()) return c;
[Link](c);

@the_DevXplained @the_dev_xplained
 ○​

}
return '\0'; // No repeated character found
}

int main() {
cout << firstRepeatedChar("abca") << endl; // Output: 'a'
return 0;
}

Java:
import [Link];

public class FirstRepeatedCharacter {

public static Character firstRepeatedChar(String s) {
HashSet<Character> seen = new HashSet<>();
for (char c : [Link]()) {
if ([Link](c)) return c;
[Link](c);
}
return null; // No repeated character found
}

public static void main(String[] args) {

[Link](firstRepeatedChar("abca")); // Output: 'a'
}
}

6. Check if two strings are rotation of each other

Algorithm

To check if two strings are rotations of each other efficiently, we use the Concatenation
Approach.

Concatenation Approach:

1.​ If the lengths of the two strings are not equal, they cannot be rotations.
2.​ Concatenate the first string with itself.
3.​ Check if the second string is a substring of this concatenated string.

@the_DevXplained @the_dev_xplained
 ○​

Time Complexity: O(N) (substring search is efficient) Space Complexity: O(N) (concatenated
string takes extra space)

Python
def are_rotations(s1, s2):
if len(s1) != len(s2):
return False
return s2 in (s1 + s1)

# Example usage:
print(are_rotations("abcd", "cdab")) # Output: True

C++
#include <iostream>
using namespace std;

bool areRotations(string s1, string s2) {

if ([Link]() != [Link]()) return false;
return (s1 + s1).find(s2) != string::npos;
}

int main() {
cout << (areRotations("abcd", "cdab") ? "True" : "False") << endl; // Output: True
return 0;
}

Java
public class StringRotationCheck {
public static boolean areRotations(String s1, String s2) {
if ([Link]() != [Link]()) return false;
return (s1 + s1).contains(s2);
}

public static void main(String[] args) {

[Link](areRotations("abcd", "cdab")); // Output: True
}
}

7. Find the longest common prefix in the array of strings:

@the_DevXplained @the_dev_xplained
 ○​

Algorithm

To find the longest common prefix among an array of strings efficiently, we use the Vertical
Scanning Approach.

Vertical Scanning Approach:

1.​ Take the first string as a reference.

2.​ Compare each character of the reference string with the corresponding character in all
other strings.
3.​ If a mismatch is found, return the common prefix found so far.
4.​ If no mismatch occurs, continue to the next character.

Time Complexity: O(N * M) (where N is the number of strings and M is the length of the shortest
string) Space Complexity: O(1) (no extra space used)

Python:
def longest_common_prefix(strs):
if not strs:
return ""

for i in range(len(strs[0])):
char = strs[0][i]
for s in strs[1:]:
if i >= len(s) or s[i] != char:
return strs[0][:i]
return strs[0]

# Example usage:
print(longest_common_prefix(["flower", "flow", "flight"])) # Output: "fl"

C++:
#include <iostream>
#include <vector>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {

if ([Link]()) return "";

for (int i = 0; i < strs[0].length(); i++) {

@the_DevXplained @the_dev_xplained
 ○​

char c = strs[0][i];
for (int j = 1; j < [Link](); j++) {
if (i >= strs[j].length() || strs[j][i] != c)
return strs[0].substr(0, i);
}
}
return strs[0];
}

int main() {
vector<string> strs = {"flower", "flow", "flight"};
cout << longestCommonPrefix(strs) << endl; // Output: "fl"
return 0;
}

Java:
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if ([Link] == 0) return "";

for (int i = 0; i < strs[0].length(); i++) {

char c = strs[0].charAt(i);
for (int j = 1; j < [Link]; j++) {
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}

public static void main(String[] args) {

String[] strs = {"flower", "flow", "flight"};
[Link](longestCommonPrefix(strs)); // Output: "fl"
}
}

8. Count vowels and consonants in a string

@the_DevXplained @the_dev_xplained
 ○​

Algorithm

To efficiently count vowels and consonants in a given string, we use the Single Pass
Approach:

Single Pass Approach:

1.​ Convert the string to lowercase to handle case insensitivity.

2.​ Use a set to store vowel characters (a, e, i, o, u).
3.​ Traverse the string once, checking each character:
○​ If it's a vowel, increase the vowel count.
○​ If it's an alphabetic character but not a vowel, increase the consonant count.
4.​ Ignore non-alphabetic characters.

Time Complexity: O(N) (where N is the length of the string) Space Complexity: O(1) (constant
extra space used)

Python:
def count_vowels_consonants(s):
vowels = set("aeiouAEIOU")
vowel_count = consonant_count = 0

for char in s:
if [Link]():
if char in vowels:
vowel_count += 1
else:
consonant_count += 1

return vowel_count, consonant_count

# Example usage:
print(count_vowels_consonants("Hello World!")) # Output: (3, 7)

C++:
#include <iostream>
#include <cctype>
using namespace std;

pair<int, int> countVowelsConsonants(const string& s) {

@the_DevXplained @the_dev_xplained
 ○​

string vowels = "aeiouAEIOU";

int vowel_count = 0, consonant_count = 0;

for (char ch : s) {
if (isalpha(ch)) {
if ([Link](ch) != string::npos)
vowel_count++;
else
consonant_count++;
}
}
return {vowel_count, consonant_count};
}

int main() {
auto result = countVowelsConsonants("Hello World!");
cout << "Vowels: " << [Link] << ", Consonants: " << [Link] << endl; // Output:
Vowels: 3, Consonants: 7
return 0;
}

Java:
public class CountVowelsConsonants {
public static int[] countVowelsConsonants(String s) {
String vowels = "aeiouAEIOU";
int vowelCount = 0, consonantCount = 0;

for (char ch : [Link]()) {

if ([Link](ch)) {
if ([Link](ch) != -1) {
vowelCount++;
} else {
consonantCount++;
}
}
}
return new int[]{vowelCount, consonantCount};
}

public static void main(String[] args) {

int[] result = countVowelsConsonants("Hello World!");

@the_DevXplained @the_dev_xplained
 ○​

[Link]("Vowels: " + result[0] + ", Consonants: " + result[1]); // Output: Vowels: 3,

Consonants: 7
}
}

9. Remove all adjacent duplicate characters from a string

Algorithm

To efficiently remove all adjacent duplicate characters from a string, we use the Stack-Based
Approach:

Stack-Based Approach:

1.​ Initialize an empty stack.

2.​ Traverse each character of the string:
○​ If the stack is not empty and the top of the stack is the same as the current
character, pop the stack (remove the duplicate).
○​ Otherwise, push the character onto the stack.
3.​ Construct the result from the stack.

This approach ensures we remove consecutive duplicates in a single pass.

Time Complexity: O(N) (where N is the length of the string) Space Complexity: O(N) (in the
worst case, storing all distinct characters in the stack)

Python:
def remove_adjacent_duplicates(s):
stack = []
for char in s:
if stack and stack[-1] == char:
[Link]()
else:
[Link](char)
return "".join(stack)

# Example usage:
print(remove_adjacent_duplicates("abbaca")) # Output: "ca"

C++:

@the_DevXplained @the_dev_xplained
 ○​

#include <iostream>
#include <stack>
using namespace std;

string removeAdjacentDuplicates(string s) {
string result = "";
for (char ch : s) {
if (![Link]() && [Link]() == ch)
result.pop_back();
else
result.push_back(ch);
}
return result;
}

int main() {
cout << removeAdjacentDuplicates("abbaca") << endl; // Output: "ca"
return 0;
}

Java:
public class RemoveAdjacentDuplicates {
public static String removeAdjacentDuplicates(String s) {
StringBuilder stack = new StringBuilder();
for (char ch : [Link]()) {
if ([Link]() > 0 && [Link]([Link]() - 1) == ch) {
[Link]([Link]() - 1);
} else {
[Link](ch);
}
}
return [Link]();
}

public static void main(String[] args) {

[Link](removeAdjacentDuplicates("abbaca")); // Output: "ca"
}
}

10. Convert a string to an integer (Implement atoi())

@the_DevXplained @the_dev_xplained
 ○​

Algorithm

To implement the atoi() function, which converts a string to an integer, we use an Iterative
Parsing Approach that handles spaces, signs, and overflow conditions.

Optimized Approach:

1.​ Trim Leading Whitespaces: Ignore any leading spaces.

2.​ Handle Sign: Check if the number is negative or positive.
3.​ Convert Digits: Process numerical characters and construct the integer.
4.​ Handle Overflow: If the number exceeds INT_MAX (2^31 - 1) or INT_MIN
(-2^31), return the respective limit.
5.​ Stop on Non-Digit Characters: Conversion stops at the first non-digit character.

Time Complexity: O(N) (where N is the length of the string) Space Complexity: O(1) (constant
extra space used)

Python
def my_atoi(s):
s = [Link]()
if not s:
return 0

sign = 1
if s[0] in ('-', '+'):
sign = -1 if s[0] == '-' else 1
s = s[1:]

res, i = 0, 0
while i < len(s) and s[i].isdigit():
res = res * 10 + int(s[i])
i += 1

res *= sign
return max(min(res, 2**31 - 1), -2**31)

# Example usage:
print(my_atoi(" -42")) # Output: -42

C++
#include <iostream>

@the_DevXplained @the_dev_xplained
 ○​

#include <climits>
using namespace std;

int myAtoi(string s) {
int i = 0, sign = 1, result = 0;
while (i < [Link]() && s[i] == ' ') i++; // Trim spaces

if (i < [Link]() && (s[i] == '-' || s[i] == '+')) { // Handle sign

sign = (s[i] == '-') ? -1 : 1;
i++;
}

while (i < [Link]() && isdigit(s[i])) {

if (result > (INT_MAX - (s[i] - '0')) / 10) // Handle overflow
return (sign == 1) ? INT_MAX : INT_MIN;

result = result * 10 + (s[i] - '0');

i++;
}
return result * sign;
}

int main() {
cout << myAtoi(" -42") << endl; // Output: -42
return 0;
}

Java:
public class StringToIntegerAtoi {
public static int myAtoi(String s) {
s = [Link]();
if ([Link]()) return 0;

int sign = 1, i = 0, result = 0;

if ([Link](0) == '-' || [Link](0) == '+') {
sign = ([Link](0) == '-') ? -1 : 1;
i++;
}

while (i < [Link]() && [Link]([Link](i))) {

if (result > (Integer.MAX_VALUE - ([Link](i) - '0')) / 10)
return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;

@the_DevXplained @the_dev_xplained
 ○​

result = result * 10 + ([Link](i) - '0');

i++;
}
return result * sign;
}

public static void main(String[] args) {

[Link](myAtoi(" -42")); // Output: -42
}
}

11. Find the longest word in a given string

Algorithm

To find the longest word in a given string efficiently, we use the Iterative Split Approach:

Optimized Approach:

1.​ Split the String: Use built-in functions to split the string into words.
2.​ Iterate Over Words: Compare lengths to determine the longest word.
3.​ Handle Edge Cases: Consider empty strings and multiple longest words.

Time Complexity: O(N) (where N is the length of the string, as we traverse it once) Space
Complexity: O(1) (only a few extra variables used)

Python
def longest_word(s):
words = [Link]()
return max(words, key=len, default="")

# Example usage:
print(longest_word("The quick brown fox jumps over the lazy dog")) # Output: "quick"

C++
#include <iostream>
#include <sstream>
using namespace std;

@the_DevXplained @the_dev_xplained
 ○​

string longestWord(string s) {
istringstream iss(s);
string word, longest;
while (iss >> word) {
if ([Link]() > [Link]()) {
longest = word;
}
}
return longest;
}

int main() {
cout << longestWord("The quick brown fox jumps over the lazy dog") << endl; // Output:
"quick"
return 0;
}

Java
public class LongestWordFinder {
public static String longestWord(String s) {
String[] words = [Link]("\\s+");
String longest = "";
for (String word : words) {
if ([Link]() > [Link]()) {
longest = word;
}
}
return longest;
}

public static void main(String[] args) {

[Link](longestWord("The quick brown fox jumps over the lazy dog")); // Output:
"quick"
}
}

12. Find all substrings of a string

Algorithm

@the_DevXplained @the_dev_xplained
 ○​

To find all substrings of a given string efficiently, we use a nested loop approach:

Optimized Approach:

1.​ Iterate Over Start Index: Use a loop to pick the starting index of the substring.
2.​ Iterate Over End Index: Use another loop to pick the ending index and extract
substrings.
3.​ Store or Process Substrings: Print or collect substrings as needed.

Time Complexity: O(N²) (since we generate substrings using two nested loops) Space
Complexity: O(1) (if printing substrings directly; O(N²) if storing them in a list)

Python
def all_substrings(s):
n = len(s)
for i in range(n):
for j in range(i + 1, n + 1):
print(s[i:j]) # Print each substring

# Example usage:
all_substrings("abc")

Output:

a
ab
abc
b
bc
c

C++
#include <iostream>
using namespace std;

void allSubstrings(string s) {
int n = [Link]();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
cout << [Link](i, j - i) << endl;

@the_DevXplained @the_dev_xplained
 ○​

}
}
}

int main() {
allSubstrings("abc");
return 0;
}

Java
public class SubstringFinder {
public static void allSubstrings(String s) {
int n = [Link]();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
[Link]([Link](i, j));
}
}
}

public static void main(String[] args) {

allSubstrings("abc");
}
}

This approach ensures that all possible substrings are efficiently extracted while keeping the
implementation simple.

Array Problems:

1. Find the unique number in an array (all other numbers appear

twice)

Algorithm

To find the unique number in an array where all other numbers appear twice, we use the XOR
(^) operator. The XOR operation has the following properties:

1.​ a ^ a = 0 (XOR of two same numbers is 0)

2.​ a ^ 0 = a (XOR of any number with 0 is the number itself)
3.​ XOR is commutative and associative

@the_DevXplained @the_dev_xplained
 ○​

By XORing all numbers together, the duplicate numbers cancel out (result in 0), and only the
unique number remains.

Time Complexity: O(N) (traverses the array once) Space Complexity: O(1) (constant space
usage)

Python
def find_unique(arr):
unique = 0
for num in arr:
unique ^= num # XOR operation
return unique

# Example usage:
print(find_unique([2, 3, 5, 3, 2])) # Output: 5

C++
#include <iostream>
using namespace std;

int findUnique(int arr[], int n) {

int unique = 0;
for (int i = 0; i < n; i++) {
unique ^= arr[i]; // XOR operation
}
return unique;
}

int main() {
int arr[] = {2, 3, 5, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findUnique(arr, n) << endl; // Output: 5
return 0;
}

Java
public class UniqueNumber {
public static int findUnique(int[] arr) {
int unique = 0;

@the_DevXplained @the_dev_xplained
 ○​

for (int num : arr) {

unique ^= num; // XOR operation
}
return unique;
}

public static void main(String[] args) {

int[] arr = {2, 3, 5, 3, 2};
[Link](findUnique(arr)); // Output: 5
}
}

This approach ensures optimal performance using bitwise XOR, making it both efficient and
memory-friendly.

2. Find pairs in an array that sum to a given target (Two Sum)

Algorithm

To find pairs in an array that sum to a given target, we use the HashMap (Dictionary)
Approach for optimal efficiency.

Optimized Approach (Using HashMap)

1.​ Traverse the array and maintain a hashmap (dictionary) to store numbers encountered.
2.​ For each number num, compute the complement target - num.
3.​ If the complement exists in the hashmap, a pair is found.
4.​ Otherwise, store num in the hashmap and continue.

Time Complexity: O(N) (single pass through the array) Space Complexity: O(N) (to store
elements in the hashmap)

Python
def find_pairs(arr, target):
seen = {}
pairs = []
for num in arr:
complement = target - num
if complement in seen:
[Link]((complement, num))
seen[num] = True

@the_DevXplained @the_dev_xplained
 ○​

return pairs

# Example usage:
print(find_pairs([2, 7, 4, 8, 1, 5], 9)) # Output: [(2, 7), (4, 5)]

C++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<pair<int, int>> findPairs(vector<int>& arr, int target) {

unordered_map<int, bool> seen;
vector<pair<int, int>> pairs;

for (int num : arr) {

int complement = target - num;
if ([Link](complement)) {
pairs.emplace_back(complement, num);
}
seen[num] = true;
}
return pairs;
}

int main() {
vector<int> arr = {2, 7, 4, 8, 1, 5};
int target = 9;
vector<pair<int, int>> result = findPairs(arr, target);
for (auto& p : result) {
cout << "(" << [Link] << ", " << [Link] << ")\n";
}
return 0;
}

Java
import [Link].*;

public class TwoSumPairs {

@the_DevXplained @the_dev_xplained
 ○​

public static List<int[]> findPairs(int[] arr, int target) {

Map<Integer, Boolean> seen = new HashMap<>();
List<int[]> pairs = new ArrayList<>();

for (int num : arr) {

int complement = target - num;
if ([Link](complement)) {
[Link](new int[]{complement, num});
}
[Link](num, true);
}
return pairs;
}

public static void main(String[] args) {

int[] arr = {2, 7, 4, 8, 1, 5};
int target = 9;
List<int[]> result = findPairs(arr, target);
for (int[] pair : result) {
[Link]("(" + pair[0] + ", " + pair[1] + ")");
}
}
}

This solution ensures we find all pairs efficiently using a hashmap-based lookup.

3. Find the maximum sum of a contiguous subarray (Kadane's algorithm)

Algorithm

To find the maximum sum of a contiguous subarray, we use Kadane's Algorithm, which
efficiently finds the largest sum in O(N) time complexity.

Kadane's Algorithm Approach

1.​ Initialize two variables:

○​ max_sum to track the maximum sum found so far.
○​ current_sum to track the sum of the current subarray.
2.​ Iterate through the array:
○​ Add the current element to current_sum.
○​ If current_sum exceeds max_sum, update max_sum.

@the_DevXplained @the_dev_xplained
 ○​

○​ If current_sum becomes negative, reset it to 0 (since a negative sum would

decrease the total sum of future subarrays).
3.​ Return max_sum as the maximum sum of any contiguous subarray.

Time Complexity: O(N) (single pass through the array) Space Complexity: O(1) (constant
space used)

Python
def max_subarray_sum(arr):
max_sum = float('-inf')
current_sum = 0

for num in arr:

current_sum += num
max_sum = max(max_sum, current_sum)
if current_sum < 0:
current_sum = 0

return max_sum

# Example usage:
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # Output: 6

C++
#include <iostream>
#include <vector>
using namespace std;

int maxSubarraySum(vector<int>& arr) {

int max_sum = INT_MIN, current_sum = 0;

for (int num : arr) {

current_sum += num;
max_sum = max(max_sum, current_sum);
if (current_sum < 0) {
current_sum = 0;
}
}
return max_sum;

@the_DevXplained @the_dev_xplained
 ○​

int main() {
vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << maxSubarraySum(arr) << endl; // Output: 6
return 0;
}

Java
public class KadaneAlgorithm {
public static int maxSubarraySum(int[] arr) {
int maxSum = Integer.MIN_VALUE, currentSum = 0;

for (int num : arr) {

currentSum += num;
maxSum = [Link](maxSum, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}

public static void main(String[] args) {

int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
[Link](maxSubarraySum(arr)); // Output: 6
}
}

This implementation ensures we find the maximum contiguous subarray sum in O(N) time
complexity efficiently.

4. Rotate an array by k positions

@the_DevXplained @the_dev_xplained
 ○​

Algorithm

To rotate an array by k positions efficiently, we use the Reverse Approach, which achieves the
result in O(N) time complexity and O(1) space complexity.

Reverse Approach

1.​ Reverse the entire array.

2.​ Reverse the first k elements.
3.​ Reverse the remaining n - k elements.

This ensures that elements are shifted correctly in O(N) time.

Time Complexity: O(N) (since we perform three passes of reversal) Space Complexity: O(1)
(no extra space used)
Python
def rotate_array(arr, k):
n = len(arr)
k %= n # Handle cases where k > n

[Link]()
arr[:k] = reversed(arr[:k])
arr[k:] = reversed(arr[k:])

return arr

# Example usage:
print(rotate_array([1, 2, 3, 4, 5, 6, 7], 3)) # Output: [5, 6, 7, 1, 2, 3, 4]

C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void rotateArray(vector<int>& arr, int k) {

int n = [Link]();

@the_DevXplained @the_dev_xplained
 ○​

k %= n; // Handle cases where k > n

reverse([Link](), [Link]());
reverse([Link](), [Link]() + k);
reverse([Link]() + k, [Link]());
}

int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6, 7};
rotateArray(arr, 3);
for (int num : arr) cout << num << " "; // Output: 5 6 7 1 2 3 4
return 0;
}

Java
import [Link].*;

public class RotateArray {

public static void rotate(int[] arr, int k) {
int n = [Link];
k %= n; // Handle cases where k > n

reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
}

private static void reverse(int[] arr, int start, int end) {

while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}

@the_DevXplained @the_dev_xplained
 ○​

public static void main(String[] args) {

int[] arr = {1, 2, 3, 4, 5, 6, 7};
rotate(arr, 3);
[Link]([Link](arr)); // Output: [5, 6, 7, 1, 2, 3, 4]
}
}

This approach ensures efficient in-place rotation using O(N) time complexity.

5. Remove duplicates from sorted array

Algorithm

To remove duplicates from a sorted array efficiently, we use the Two-Pointer Approach. This
method ensures an O(N) time complexity with O(1) extra space.

Two-Pointer Approach

1.​ Use a pointer j to track the position of unique elements.

2.​ Iterate through the array with a pointer i, comparing arr[i] with arr[j].
3.​ If arr[i] is different from arr[j], increment j and update arr[j].
4.​ Return the new length of the unique elements.

Time Complexity: O(N) (traversing the array once) Space Complexity: O(1) (modifying the
array in-place)

Python
def remove_duplicates(arr):
if not arr:
return 0

j = 0 # Pointer for the unique elements

for i in range(1, len(arr)):
if arr[i] != arr[j]:
j += 1
arr[j] = arr[i]

@the_DevXplained @the_dev_xplained
 ○​

return j + 1 # New length of unique elements

# Example usage:
arr = [1, 1, 2, 2, 3, 4, 4, 5]
new_length = remove_duplicates(arr)
print(arr[:new_length]) # Output: [1, 2, 3, 4, 5]

C++
#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& arr) {

if ([Link]()) return 0;

int j = 0;
for (int i = 1; i < [Link](); i++) {
if (arr[i] != arr[j]) {
j++;
arr[j] = arr[i];
}
}
return j + 1;
}

int main() {
vector<int> arr = {1, 1, 2, 2, 3, 4, 4, 5};
int newLength = removeDuplicates(arr);
for (int i = 0; i < newLength; i++) cout << arr[i] << " "; // Output: 1 2 3 4 5
return 0;
}

Java
public class RemoveDuplicates {
public static int removeDuplicates(int[] arr) {
if ([Link] == 0) return 0;

int j = 0;

@the_DevXplained @the_dev_xplained
 ○​

for (int i = 1; i < [Link]; i++) {

if (arr[i] != arr[j]) {
J++;
arr[j] = arr[i];
}
}
return j + 1;
}

public static void main(String[] args) {

int[] arr = {1, 1, 2, 2, 3, 4, 4, 5};
int newLength = removeDuplicates(arr);
for (int i = 0; i < newLength; i++) {
[Link](arr[i] + " "); // Output: 1 2 3 4 5
}
}
}

This approach modifies the array in-place and ensures O(N) time complexity.

6. Find the Missing Number in a Sorted Array

Algorithm: Binary Search

1.​ Use binary search to find the missing number.

2.​ Check if the middle element matches its expected position.
3.​ If not, the missing number is in the left half; otherwise, search in the right half.
4.​ Continue until the missing number is identified.

Time Complexity: O(log N)​

Space Complexity: O(1)

Python
def find_missing(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] > mid + 1:
right = mid

@the_DevXplained @the_dev_xplained
 ○​

else:
left = mid + 1
return left + 1

# Example usage:
arr = [1, 2, 3, 4, 6, 7, 8]
print(find_missing(arr)) # Output: 5

C++
#include <iostream>
using namespace std;

int findMissing(int arr[], int n) {

int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] > mid + 1)
right = mid;
else
left = mid + 1;
}
return left + 1;
}

int main() {
int arr[] = {1, 2, 3, 4, 6, 7, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMissing(arr, n) << endl; // Output: 5
return 0;
}

Java
public class MissingNumber {
public static int findMissing(int[] arr) {
int left = 0, right = [Link] - 1;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] > mid + 1)
right = mid;

@the_DevXplained @the_dev_xplained
 ○​

else
left = mid + 1;
}
return left + 1;
}

public static void main(String[] args) {

int[] arr = {1, 2, 3, 4, 6, 7, 8};
[Link](findMissing(arr)); // Output: 5
}
}

7. Second Largest Element in an Array

Optimized Approach: Single Pass Scan

1.​ Initialize two variables to track the largest and second largest elements.
2.​ Iterate through the array to update these variables accordingly.
3.​ Return the second largest element.

Time Complexity: O(N)​

Space Complexity: O(1)

Python
def second_largest(arr):
first, second = float('-inf'), float('-inf')
for num in arr:
if num > first:
second, first = first, num
elif num > second and num != first:
second = num
return second if second != float('-inf') else -1

# Example usage:
arr = [10, 20, 4, 45, 99]
print(second_largest(arr)) # Output: 45

C++
#include <iostream>
using namespace std;

@the_DevXplained @the_dev_xplained
 ○​

int secondLargest(int arr[], int n) {

int first = INT_MIN, second = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
} else if (arr[i] > second && arr[i] != first) {
second = arr[i];
}
}
return (second == INT_MIN) ? -1 : second;
}

int main() {
int arr[] = {10, 20, 4, 45, 99};
int n = sizeof(arr) / sizeof(arr[0]);
cout << secondLargest(arr, n) << endl; // Output: 45
return 0;
}

Java
public class SecondLargest {
public static int secondLargest(int[] arr) {
int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
for (int num : arr) {
if (num > first) {
second = first;
first = num;
} else if (num > second && num != first) {
second = num;
}
}
return (second == Integer.MIN_VALUE) ? -1 : second;
}

public static void main(String[] args) {

int[] arr = {10, 20, 4, 45, 99};
[Link](secondLargest(arr)); // Output: 45
}
}

@the_DevXplained @the_dev_xplained
 ○​

8. Reverse an Array

Optimized Approach: Two-Pointer Method

1.​ Use two pointers: one at the beginning and one at the end.
2.​ Swap the elements at these positions.
3.​ Move the pointers towards the center until they meet.

Time Complexity: O(N)​

Space Complexity: O(1)

Python
def reverse_array(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr

# Example usage:
arr = [1, 2, 3, 4, 5]
print(reverse_array(arr)) # Output: [5, 4, 3, 2, 1]

C++
#include <iostream>
using namespace std;

void reverseArray(int arr[], int n) {

int left = 0, right = n - 1;
while (left < right) {
swap(arr[left], arr[right]);
left++;
right--;
}
}

int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
reverseArray(arr, n);

@the_DevXplained @the_dev_xplained
 ○​

for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}

Java
public class ReverseArray {
public static void reverseArray(int[] arr) {
int left = 0, right = [Link] - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
reverseArray(arr);
for (int num : arr) [Link](num + " ");
}
}

9. Move All Zeros to the End of an Array

Optimized Approach: Two-Pointer Method

1.​ Maintain a pointer for the position to place non-zero elements.

2.​ Iterate through the array, moving non-zero elements to the front.
3.​ Fill the remaining positions with zeros.

Time Complexity: O(N)​

Space Complexity: O(1)

Python
def move_zeros(arr):
pos = 0 # Position to place non-zero elements
for num in arr:
if num != 0:
arr[pos] = num
pos += 1

@the_DevXplained @the_dev_xplained
 ○​

for i in range(pos, len(arr)):

arr[i] = 0
return arr

# Example usage:
arr = [0, 1, 0, 3, 12]
print(move_zeros(arr)) # Output: [1, 3, 12, 0, 0]

C++
#include <iostream>
using namespace std;

void moveZeros(int arr[], int n) {

int pos = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
swap(arr[i], arr[pos]);
pos++;
}
}
}

int main() {
int arr[] = {0, 1, 0, 3, 12};
int n = sizeof(arr) / sizeof(arr[0]);
moveZeros(arr, n);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}

Java
public class MoveZeros {
public static void moveZeros(int[] arr) {
int pos = 0;
for (int num : arr) {
if (num != 0) arr[pos++] = num;
}
while (pos < [Link]) arr[pos++] = 0;
}
public static void main(String[] args) {

@the_DevXplained @the_dev_xplained
 ○​

int[] arr = {0, 1, 0, 3, 12};

moveZeros(arr);
for (int num : arr) [Link](num + " ");
}
}

10. Find the intersection of two sorted arrays

Algorithm:

1.​ Use two pointers, one for each array.

2.​ Compare elements at both pointers:
○​ If they are equal, add to the result and move both pointers.
○​ If the element in the first array is smaller, move that pointer.
○​ Otherwise, move the second pointer.
3.​ Continue until one of the arrays is fully traversed.

Time Complexity: O(N + M)​

Space Complexity: O(1) (excluding output storage)

Python
def intersection(arr1, arr2):
i, j = 0, 0
result = []
while i < len(arr1) and j < len(arr2):
if arr1[i] == arr2[j]:
[Link](arr1[i])
i += 1
j += 1
elif arr1[i] < arr2[j]:
i += 1
else:
j += 1
return result

# Example usage:
print(intersection([1, 2, 4, 5, 6], [2, 3, 5, 7])) # Output: [2, 5]

C++
#include <iostream>

@the_DevXplained @the_dev_xplained
 ○​

#include <vector>
using namespace std;

vector<int> intersection(vector<int>& arr1, vector<int>& arr2) {

int i = 0, j = 0;
vector<int> result;
while (i < [Link]() && j < [Link]()) {
if (arr1[i] == arr2[j]) {
result.push_back(arr1[i]);
i++, j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
return result;
}

int main() {
vector<int> arr1 = {1, 2, 4, 5, 6};
vector<int> arr2 = {2, 3, 5, 7};
vector<int> result = intersection(arr1, arr2);
for (int num : result) cout << num << " ";
return 0;
}
Java
import [Link].*;

class Intersection {
public static List<Integer> intersection(int[] arr1, int[] arr2) {
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
while (i < [Link] && j < [Link]) {
if (arr1[i] == arr2[j]) {
[Link](arr1[i]);
i++;
j++;

@the_DevXplained @the_dev_xplained
 ○​

} else if (arr1[i] < arr2[j]) {

i++;
} else {
j++;
}
}
return result;
}

public static void main(String[] args) {

int[] arr1 = {1, 2, 4, 5, 6};
int[] arr2 = {2, 3, 5, 7};
[Link](intersection(arr1, arr2)); // Output: [2, 5]
}
}

11. Find the Union of Two Unsorted Arrays

Algorithm

1.​ Use a HashSet (or unordered_set in C++) to store unique elements.

2.​ Insert all elements from the first array into the set.
3.​ Insert all elements from the second array into the set.
4.​ Convert the set to a list or vector to return the final result.
5.​ The set ensures only unique elements are stored.

Time Complexity: O(N + M) (where N and M are sizes of the two arrays) Space Complexity:
O(N + M) (for storing unique elements)

Python
def union_of_arrays(arr1, arr2):
return list(set(arr1) | set(arr2))

# Example usage:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(union_of_arrays(arr1, arr2)) # Output: [1, 2, 3, 4, 5, 6, 7]

C++

@the_DevXplained @the_dev_xplained
 ○​

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

vector<int> unionOfArrays(vector<int>& arr1, vector<int>& arr2) {

unordered_set<int> uniqueElements([Link](), [Link]());
[Link]([Link](), [Link]());
return vector<int>([Link](), [Link]());
}

int main() {
vector<int> arr1 = {1, 2, 3, 4, 5};
vector<int> arr2 = {3, 4, 5, 6, 7};
vector<int> result = unionOfArrays(arr1, arr2);
for (int num : result) cout << num << " "; // Output: 1 2 3 4 5 6 7
return 0;
}

Java
import [Link].*;

public class UnionOfArrays {

public static Set<Integer> unionOfArrays(int[] arr1, int[] arr2) {
Set<Integer> uniqueElements = new HashSet<>();
for (int num : arr1) [Link](num);
for (int num : arr2) [Link](num);
return uniqueElements;
}

public static void main(String[] args) {

int[] arr1 = {1, 2, 3, 4, 5};
int[] arr2 = {3, 4, 5, 6, 7};
[Link](unionOfArrays(arr1, arr2)); // Output: [1, 2, 3, 4, 5, 6, 7]
}
}

12. Find the First Repeating Element in an Array

Algorithm

@the_DevXplained @the_dev_xplained
 ○​

1.​ Use a HashSet (unordered_set in C++) to track seen elements.

2.​ Traverse the array from left to right.
3.​ If an element is already present in the set, return it as the first repeating element.
4.​ If no repeating element is found, return -1.

Time Complexity: O(N) (since we traverse the array once and insert/look up elements in a
HashSet in O(1) time on average) Space Complexity: O(N) (for storing elements in the
HashSet)

Python
def first_repeating_element(arr):
seen = set()
for num in arr:
if num in seen:
return num
[Link](num)
return -1

# Example usage:
arr = [10, 5, 3, 4, 3, 5, 6]
print(first_repeating_element(arr)) # Output: 5

C++
#include <iostream>
#include <unordered_set>
using namespace std;

int firstRepeatingElement(int arr[], int n) {

unordered_set<int> seen;
for (int i = 0; i < n; i++) {
if ([Link](arr[i]) != [Link]())
return arr[i];
[Link](arr[i]);
}
return -1;
}

int main() {
int arr[] = {10, 5, 3, 4, 3, 5, 6};

@the_DevXplained @the_dev_xplained
 ○​

int n = sizeof(arr) / sizeof(arr[0]);

cout << firstRepeatingElement(arr, n) << endl; // Output: 5
return 0;
}

Java
import [Link].*;

public class FirstRepeatingElement {

public static int firstRepeatingElement(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if ([Link](num)) return num;
[Link](num);
}
return -1;
}

public static void main(String[] args) {

int[] arr = {10, 5, 3, 4, 3, 5, 6};
[Link](firstRepeatingElement(arr)); // Output: 5
}

13. Find the Element That Appears More Than n/2 Times (Majority Element)

Algorithm (Boyer-Moore Voting Algorithm)

1.​ Initialize two variables: candidate to store a potential majority element and count to
track its frequency.
2.​ Traverse the array:
○​ If count is 0, set candidate to the current element.
○​ If the current element is the same as candidate, increase count.
○​ Otherwise, decrease count.
3.​ The remaining candidate will be the majority element.
4.​ Verify by counting occurrences (optional if the problem guarantees existence).

Time Complexity: O(N)​

Space Complexity: O(1)

@the_DevXplained @the_dev_xplained
 ○​

Python
def majority_element(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate

# Example usage:
arr = [3, 3, 4, 2, 3, 3, 3]
print(majority_element(arr)) # Output: 3

C++
#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& nums) {

int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate;
}

int main() {
vector<int> arr = {3, 3, 4, 2, 3, 3, 3};
cout << majorityElement(arr) << endl; // Output: 3
return 0;
}

Java
public class MajorityElement {
public static int majorityElement(int[] nums) {
int candidate = 0, count = 0;
for (int num : nums) {

@the_DevXplained @the_dev_xplained
 ○​

if (count == 0) candidate = num;

count += (num == candidate) ? 1 : -1;
}
return candidate;
}

public static void main(String[] args) {

int[] arr = {3, 3, 4, 2, 3, 3, 3};
[Link](majorityElement(arr)); // Output: 3
}
}

14. Find the Longest Consecutive Sequence in an Unsorted Array

Algorithm

1.​ Use a HashSet (or unordered_set in C++) to store all unique elements of the array.
2.​ Iterate through each element and check if it is the start of a sequence (i.e., num - 1 is
not present in the set).
3.​ If it is the start of a sequence, count the length of the consecutive numbers.
4.​ Update the maximum sequence length encountered.

Time Complexity: O(N) (Each number is processed only once.)​

Space Complexity: O(N) (For storing elements in a set.)

Python
def longest_consecutive(nums):
num_set = set(nums)
longest_streak = 0

for num in num_set:

if num - 1 not in num_set:
current_num = num
current_streak = 1

while current_num + 1 in num_set:

current_num += 1
current_streak += 1

longest_streak = max(longest_streak, current_streak)

@the_DevXplained @the_dev_xplained
 ○​

return longest_streak

# Example usage:
nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive(nums)) # Output: 4

C++
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int longestConsecutive(vector<int>& nums) {

unordered_set<int> numSet([Link](), [Link]());
int longestStreak = 0;

for (int num : numSet) {

if ([Link](num - 1) == [Link]()) {
int currentNum = num;
int currentStreak = 1;

while ([Link](currentNum + 1) != [Link]()) {

currentNum++;
currentStreak++;
}

longestStreak = max(longestStreak, currentStreak);

}
}

return longestStreak;
}

int main() {
vector<int> nums = {100, 4, 200, 1, 3, 2};
cout << longestConsecutive(nums) << endl; // Output: 4
return 0;
}

@the_DevXplained @the_dev_xplained
 ○​

Java
import [Link];

public class LongestConsecutiveSequence {

public static int longestConsecutive(int[] nums) {
HashSet<Integer> numSet = new HashSet<>();
for (int num : nums) [Link](num);

int longestStreak = 0;

for (int num : numSet) {

if () {
int currentNum = num;
int currentStreak = 1;

while ([Link](currentNum + 1)) {

currentNum++;
currentStreak++;
}

longestStreak = [Link](longestStreak, currentStreak);

}
}

return longestStreak;
}

public static void main(String[] args) {

int[] nums = {100, 4, 200, 1, 3, 2};
[Link](longestConsecutive(nums)); // Output: 4
}
}

15. Sort an array of 0s, 1s, and 2s (Dutch National Flag Problem)

Algorithm

1.​ Use three pointers: low, mid, and high.

2.​ low points to the start of the array, mid is used for traversal, and high points to the end.

@the_DevXplained @the_dev_xplained
 ○​

3.​ Iterate while mid <= high:

○​ If arr[mid] == 0, swap arr[mid] with arr[low], increment both low and
mid.
○​ If arr[mid] == 1, move mid forward.
○​ If arr[mid] == 2, swap arr[mid] with arr[high] and decrement high.

Time Complexity: O(N) Space Complexity: O(1)

Python
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1

# Example usage:
arr = [2, 0, 1, 2, 1, 0]
sort_colors(arr)
print(arr) # Output: [0, 0, 1, 1, 2, 2]

C++
#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {

int low = 0, mid = 0, high = [Link]() - 1;
while (mid <= high) {
if (nums[mid] == 0) swap(nums[mid++], nums[low++]);
else if (nums[mid] == 1) mid++;
else swap(nums[mid], nums[high--]);
}

@the_DevXplained @the_dev_xplained
 ○​

int main() {
vector<int> arr = {2, 0, 1, 2, 1, 0};
sortColors(arr);
for (int num : arr) cout << num << " "; // Output: 0 0 1 1 2 2
return 0;
}

Java
import [Link].*;

public class SortColors {

public static void sortColors(int[] nums) {
int low = 0, mid = 0, high = [Link] - 1;
while (mid <= high) {
if (nums[mid] == 0) {
int temp = nums[low];
nums[low++] = nums[mid];
nums[mid++] = temp;
} else if (nums[mid] == 1) {
mid++;
} else {
int temp = nums[mid];
nums[mid] = nums[high];
nums[high--] = temp;
}
}
}

public static void main(String[] args) {

int[] arr = {2, 0, 1, 2, 1, 0};
sortColors(arr);
[Link]([Link](arr)); // Output: [0, 0, 1, 1, 2, 2]
}
}

@the_DevXplained @the_dev_xplained
 ○​

16. Find the product of all elements except the current element (without
division)

Algorithm:

1.​ Compute left product for each element.

2.​ Compute right product for each element.
3.​ Multiply left and right products to get the final result.

Time Complexity: O(N) Space Complexity: O(1)

Python

def product_except_self(nums):

n = len(nums)

result = [1] * n
left = 1
for i in range(n):
result[i] = left
left *= nums[i]
right = 1
for i in range(n-1, -1, -1):
result[i] *= right
right *= nums[i]
return result

print(product_except_self([1,2,3,4])) # Output: [24, 12, 8, 6]

C++
#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {

int n = [Link]();
vector<int> result(n, 1);
int left = 1, right = 1;
for (int i = 0; i < n; i++) {

@the_DevXplained @the_dev_xplained
 ○​

result[i] *= left;
left *= nums[i];
}
for (int i = n - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}

Java
import [Link].*;

public class ProductExceptSelf {

public static int[] productExceptSelf(int[] nums) {
int n = [Link];
int[] result = new int[n];
[Link](result, 1);
int left = 1, right = 1;
for (int i = 0; i < n; i++) {
result[i] *= left;
left *= nums[i];
}
for (int i = n - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}
}

17. Find the subarray with a given sum in a non-negative array

Algorithm

1.​ Use the Sliding Window Technique with two pointers (start and end).
2.​ Maintain a current_sum to store the sum of elements between start and end.

@the_DevXplained @the_dev_xplained
 ○​

3.​ Traverse the array using end:

○​ Add arr[end] to current_sum.
○​ If current_sum exceeds the target, move start forward to reduce it.
○​ If current_sum equals the target, return the subarray.
4.​ If no subarray is found, return an indication of failure.

Time Complexity: O(N) Space Complexity: O(1)

Python
def subarray_sum(arr, target):
start, current_sum = 0, 0
for end in range(len(arr)):
current_sum += arr[end]
while current_sum > target:
current_sum -= arr[start]
start += 1
if current_sum == target:
return arr[start:end+1]
return []

# Example usage:
arr = [1, 4, 20, 3, 10, 5]
target = 33
print(subarray_sum(arr, target)) # Output: [20, 3, 10]

C++
#include <iostream>
#include <vector>
using namespace std;

vector<int> subarraySum(vector<int>& arr, int target) {

int start = 0, current_sum = 0;
for (int end = 0; end < [Link](); end++) {
current_sum += arr[end];
while (current_sum > target) {
current_sum -= arr[start];
start++;
}
if (current_sum == target) {

@the_DevXplained @the_dev_xplained
 ○​

return vector<int>([Link]() + start, [Link]() + end + 1);

}
}
return {};
}

int main() {
vector<int> arr = {1, 4, 20, 3, 10, 5};
int target = 33;
vector<int> result = subarraySum(arr, target);
for (int num : result) cout << num << " ";
return 0;
}

Java
import [Link].*;

public class SubarraySum {

public static List<Integer> subarraySum(int[] arr, int target) {
int start = 0, current_sum = 0;
for (int end = 0; end < [Link]; end++) {
current_sum += arr[end];
while (current_sum > target) {
current_sum -= arr[start++];
}
if (current_sum == target) {
return [Link]([Link](arr, start, end + 1));
}
}
return [Link]();
}

public static void main(String[] args) {

int[] arr = {1, 4, 20, 3, 10, 5};
int target = 33;
[Link](subarraySum(arr, target)); // Output: [20, 3, 10]
}
}

@the_DevXplained @the_dev_xplained
 ○​

18. Find the smallest missing positive number in an array

Algorithm

1.​ Use the index as a hash key:

○​ Iterate through the array and place each positive integer in its correct position
(arr[i] = i + 1) if possible.
2.​ Traverse the array:
○​ The first index where arr[i] != i + 1 gives the missing positive number.
○​ If all numbers are in place, the missing number is n + 1.

Time Complexity: O(N) Space Complexity: O(1)

Python
def find_smallest_missing_positive(arr):
n = len(arr)
for i in range(n):
while 1 <= arr[i] <= n and arr[arr[i] - 1] != arr[i]:
arr[arr[i] - 1], arr[i] = arr[i], arr[arr[i] - 1] # Swap

for i in range(n):
if arr[i] != i + 1:
return i + 1
return n + 1

# Example usage:
arr = [3, 4, -1, 1]
print(find_smallest_missing_positive(arr)) # Output: 2

C++

#include <iostream>
#include <vector>
using namespace std;

int findSmallestMissingPositive(vector<int>& arr) {

int n = [Link]();
for (int i = 0; i < n; i++) {
while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {

@the_DevXplained @the_dev_xplained
 ○​

swap(arr[i], arr[arr[i] - 1]);

}
}

for (int i = 0; i < n; i++) {

if (arr[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}

int main() {
vector<int> arr = {3, 4, -1, 1};
cout << findSmallestMissingPositive(arr) << endl; // Output: 2
return 0;
}

Java
import [Link].*;

public class SmallestMissingPositive {

public static int findSmallestMissingPositive(int[] arr) {
int n = [Link];
for (int i = 0; i < n; i++) {
while (arr[i] > 0 && arr[i] <= n && arr[arr[i] - 1] != arr[i]) {
int temp = arr[i];
arr[i] = arr[temp - 1];
arr[temp - 1] = temp;
}
}

for (int i = 0; i < n; i++) {

if (arr[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}

@the_DevXplained @the_dev_xplained
 ○​

public static void main(String[] args) {

int[] arr = {3, 4, -1, 1};
[Link](findSmallestMissingPositive(arr)); // Output: 2
}
}

Dictionary Problems:

1. Group anagrams from a list of strings

Algorithm:

1.​ Use a hashmap to store sorted versions of words as keys.

2.​ Iterate through the list and group words by their sorted versions.
3.​ Return the grouped anagrams. Time Complexity: O(NK log K) (sorting each word)
Space Complexity: O(NK)

Python
from collections import defaultdict

def group_anagrams(words):
anagrams = defaultdict(list)
for word in words:
anagrams[tuple(sorted(word))].append(word)
return list([Link]())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& words) {

unordered_map<string, vector<string>> anagrams;
for (string word : words) {

@the_DevXplained @the_dev_xplained
 ○​

string sortedWord = word;

sort([Link](), [Link]());
anagrams[sortedWord].push_back(word);
}
vector<vector<string>> result;
for (auto& pair : anagrams) result.push_back([Link]);
return result;
}

int main() {
vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
vector<vector<string>> result = groupAnagrams(words);
for (auto group : result) {
for (string word : group) cout << word << " ";
cout << endl;
}
return 0;
}

Java
import [Link].*;

public class GroupAnagrams {

public static List<List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> anagrams = new HashMap<>();
for (String word : words) {
char[] sortedChars = [Link]();
[Link](sortedChars);
String sortedWord = new String(sortedChars);
[Link](sortedWord, k -> new ArrayList<>()).add(word);
}
return new ArrayList<>([Link]());
}

public static void main(String[] args) {

String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
[Link](groupAnagrams(words));
}
}

@the_DevXplained @the_dev_xplained
 ○​

2. Find the first non-repeating character in a string

Algorithm:

1.​ Use a hashmap to store character frequencies.

2.​ Iterate through the string and return the first character with frequency 1. Time
Complexity: O(N) Space Complexity: O(1) (since characters are limited)

Python
from collections import Counter

def first_non_repeating(s):
freq = Counter(s)
for char in s:
if freq[char] == 1:
return char
return None

print(first_non_repeating("swiss"))

C++
#include <iostream>
#include <unordered_map>
using namespace std;

char firstNonRepeating(string s) {
unordered_map<char, int> freq;
for (char ch : s) freq[ch]++;
for (char ch : s) if (freq[ch] == 1) return ch;
return '_';
}

int main() {
cout << firstNonRepeating("swiss") << endl;
return 0;
}

Java
import [Link].*;

@the_DevXplained @the_dev_xplained
 ○​

public class FirstNonRepeating {

public static char firstNonRepeating(String s) {
Map<Character, Integer> freq = new HashMap<>();
for (char ch : [Link]()) [Link](ch, [Link](ch, 0) + 1);
for (char ch : [Link]()) if ([Link](ch) == 1) return ch;
return '_';
}

public static void main(String[] args) {

[Link](firstNonRepeating("swiss"));
}
}

3. Count the frequency of each element in a list

Algorithm:

1.​ Use a hashmap (dictionary) to store the frequency of each element.

2.​ Traverse the list and update the count in the hashmap.
3.​ Output the frequency of each element. Time Complexity: O(N) Space Complexity:
O(N)

Python
from collections import Counter

def count_frequency(arr):
freq = Counter(arr)
return dict(freq)

print(count_frequency([1, 2, 2, 3, 3, 3, 4]))
# Output: {1: 1, 2: 2, 3: 3, 4: 1}

C++
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

@the_DevXplained @the_dev_xplained
 ○​

void countFrequency(vector<int> arr) {

unordered_map<int, int> freq;
for (int num : arr) freq[num]++;
for (auto pair : freq) cout << [Link] << " : " << [Link] << endl;
}

int main() {
vector<int> arr = {1, 2, 2, 3, 3, 3, 4};
countFrequency(arr);
return 0;
}
// Output: 1 : 1\n2 : 2\n3 : 3\n4 : 1

Java
import [Link].*;

public class FrequencyCounter {

public static void countFrequency(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr) [Link](num, [Link](num, 0) + 1);
for ([Link]<Integer, Integer> entry : [Link]())
[Link]([Link]() + " : " + [Link]());
}

public static void main(String[] args) {

int[] arr = {1, 2, 2, 3, 3, 3, 4};
countFrequency(arr);
}
}
// Output: 1 : 1\n2 : 2\n3 : 3\n4 : 1

4. Find the top k most frequent elements in an array

Algorithm:

1.​ Use a hashmap to store the frequency of each element.

2.​ Use a min heap to keep track of the top k elements.
3.​ Extract k most frequent elements from the heap. Time Complexity: O(N log k) Space
Complexity: O(N)

@the_DevXplained @the_dev_xplained
 ○​

Python
from collections import Counter
import heapq

def top_k_frequent(arr, k):

freq = Counter(arr)
return [num for num, count in [Link](k, [Link](), key=lambda x: x[1])]

print(top_k_frequent([1,1,1,2,2,3,3,3,3,4], 2))
# Output: [3, 1]

C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {

unordered_map<int, int> freq;
for (int num : nums) freq[num]++;
priority_queue<pair<int, int>> maxHeap;
for (auto pair : freq) [Link]({[Link], [Link]});
vector<int> result;
while (k-- && ![Link]()) {
result.push_back([Link]().second);
[Link]();
}
return result;
}

int main() {
vector<int> nums = {1,1,1,2,2,3,3,3,3,4};
int k = 2;
vector<int> result = topKFrequent(nums, k);
for (int num : result) cout << num << " ";
return 0;
}
// Output: 3 1

@the_DevXplained @the_dev_xplained
 ○​

Java
import [Link].*;

public class TopKFrequent {

public static List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) [Link](num, [Link](num, 0) + 1);
PriorityQueue<[Link]<Integer, Integer>> maxHeap =
new PriorityQueue<>((a, b) -> [Link]() - [Link]());
[Link]([Link]());
List<Integer> result = new ArrayList<>();
while (k-- > 0 && ![Link]()) [Link]([Link]().getKey());
return result;
}

public static void main(String[] args) {

int[] nums = {1,1,1,2,2,3,3,3,3,4};
int k = 2;
[Link](topKFrequent(nums, k));
}
}
// Output: [3, 1]

5. Find the most frequent word in a paragraph

Algorithm:

1.​ Convert the paragraph into a list of words.

2.​ Use a hashmap to store word frequencies.
3.​ Return the word with the highest frequency. Time Complexity: O(N) Space
Complexity: O(N)

Python
from collections import Counter
import re

def most_frequent_word(paragraph):
words = [Link](r'\w+', [Link]())
freq = Counter(words)
return max(freq, key=[Link])

@the_DevXplained @the_dev_xplained
 ○​

print(most_frequent_word("The quick brown fox jumps over the lazy dog. The fox was quick."))
# Output: "the"

C++
#include <iostream>
#include <sstream>
#include <unordered_map>
using namespace std;

string mostFrequentWord(string paragraph) {

unordered_map<string, int> freq;
stringstream ss(paragraph);
string word, maxWord;
int maxFreq = 0;
while (ss >> word) {
freq[word]++;
if (freq[word] > maxFreq) {
maxFreq = freq[word];
maxWord = word;
}
}
return maxWord;
}

int main() {
string paragraph = "The quick brown fox jumps over the lazy dog. The fox was quick.";
cout << mostFrequentWord(paragraph) << endl;
return 0;
}
// Output: "the"

Java
import [Link].*;

public class MostFrequentWord {

public static String mostFrequentWord(String paragraph) {
String[] words = [Link]().split("\\W+");
Map<String, Integer> freq = new HashMap<>();

@the_DevXplained @the_dev_xplained
 ○​

String maxWord = "";

int maxFreq = 0;
for (String word : words) {
[Link](word, [Link](word, 0) + 1);
if ([Link](word) > maxFreq) {
maxFreq = [Link](word);
maxWord = word;
}
}
return maxWord;
}
}
// Output: "the"

6. Find Common Elements in Three Sorted Arrays

Algorithm:

1.​ Use three pointers (i, j, k) to traverse three sorted arrays.

2.​ If arr1[i] == arr2[j] == arr3[k], add it to the result and increment all pointers.
3.​ If the smallest element is not common, move the pointer pointing to the smallest value.
4.​ Continue until one of the arrays is fully traversed.

Python

def find_common_elements(arr1, arr2, arr3):

i=j=k=0
result = []
while i < len(arr1) and j < len(arr2) and k < len(arr3):
if arr1[i] == arr2[j] == arr3[k]:
[Link](arr1[i])
i += 1
j += 1
k += 1
elif arr1[i] < arr2[j]:
i += 1
elif arr2[j] < arr3[k]:
j += 1
else:
k += 1
return result

@the_DevXplained @the_dev_xplained
 ○​

C++

#include <iostream>
#include <vector>
using namespace std;
vector<int> findCommonElements(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
int i = 0, j = 0, k = 0;
vector<int> result;
while (i < [Link]() && j < [Link]() && k < [Link]()) {
if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
result.push_back(arr1[i]);
i++; j++; k++;
} else if (arr1[i] < arr2[j]) {
i++;
} else if (arr2[j] < arr3[k]) {
j++;
} else {
k++;
}
}
return result;
}

Java

import [Link].*;
public class CommonElements {
public static List<Integer> findCommonElements(int[] arr1, int[] arr2, int[] arr3) {
int i = 0, j = 0, k = 0;
List<Integer> result = new ArrayList<>();
while (i < [Link] && j < [Link] && k < [Link]) {
if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
[Link](arr1[i]);
i++; j++; k++;
} else if (arr1[i] < arr2[j]) {
i++;
} else if (arr2[j] < arr3[k]) {
j++;
} else {

@the_DevXplained @the_dev_xplained
 ○​

k++;
}
}
return result;
}
}

7. Find the Longest Substring Without Repeating Characters

Algorithm:

1.​ Use a sliding window approach with two pointers (left and right).
2.​ Use a hash set to track characters in the window.
3.​ Expand right pointer if the character is unique; shrink left if it's a duplicate.
4.​ Update max length accordingly.

Python

def longest_substring(s):
char_set = set()
left = max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length

C++

#include <iostream>
#include <unordered_set>
using namespace std;
int longestSubstring(string s) {
unordered_set<char> charSet;
int left = 0, maxLength = 0;
for (int right = 0; right < [Link](); right++) {
while ([Link](s[right]) != [Link]()) {
[Link](s[left]);

@the_DevXplained @the_dev_xplained
 ○​

left++;
}
[Link](s[right]);
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}

Java

import [Link].*;
public class LongestSubstring {
public static int longestSubstring(String s) {
Set<Character> charSet = new HashSet<>();
int left = 0, maxLength = 0;
for (int right = 0; right < [Link](); right++) {
while ([Link]([Link](right))) {
[Link]([Link](left));
left++;
}
[Link]([Link](right));
maxLength = [Link](maxLength, right - left + 1);
}
return maxLength;
}
}

8. Check If Two Arrays Are Equal (Ignoring Order)

Algorithm:

1.​ If the lengths of both arrays are different, return false.

2.​ Use a hash map to store the frequency of elements in the first array.
3.​ Traverse the second array and decrement the frequency count.
4.​ If any frequency goes negative, return false.
5.​ If all counts are zero at the end, return true.

Python

from collections import Counter

@the_DevXplained @the_dev_xplained
 ○​

def are_arrays_equal(arr1, arr2):

return Counter(arr1) == Counter(arr2)

C++

#include <iostream>
#include <unordered_map>
using namespace std;
bool areArraysEqual(vector<int>& arr1, vector<int>& arr2) {
if ([Link]() != [Link]()) return false;
unordered_map<int, int> freq;
for (int num : arr1) freq[num]++;
for (int num : arr2) {
if (freq[num] == 0) return false;
freq[num]--;
}
return true;
}

Java

import [Link].*;
public class ArrayEquality {
public static boolean areArraysEqual(int[] arr1, int[] arr2) {
if ([Link] != [Link]) return false;
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr1) [Link](num, [Link](num, 0) + 1);
for (int num : arr2) {
if ( || [Link](num) == 0) return false;
[Link](num, [Link](num) - 1);
}
return true;
}
}

9. Find all elements in an array that appear more than ⌊n/3⌋ times

Algorithm:

@the_DevXplained @the_dev_xplained
 ○​

1.​ Use Boyer-Moore Voting Algorithm to identify at most two potential candidates.
2.​ Count occurrences of these candidates in the array.
3.​ Return elements that appear more than ⌊n/3⌋ times. Time Complexity: O(N) Space
Complexity: O(1)

Python
from collections import Counter

def find_majority_elements(arr):
if not arr:
return []

candidate1, candidate2, count1, count2 = None, None, 0, 0

for num in arr:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = num, 1
elif count2 == 0:
candidate2, count2 = num, 1
else:
count1 -= 1
count2 -= 1

return [num for num in (candidate1, candidate2) if [Link](num) > len(arr) // 3]

print(find_majority_elements([3,3,2,2,2,1,1,1,1])) # Output: [1, 2]

C++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> findMajorityElements(vector<int>& nums) {

int candidate1 = -1, candidate2 = -1, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;

@the_DevXplained @the_dev_xplained
 ○​

else if (count1 == 0) candidate1 = num, count1 = 1;

else if (count2 == 0) candidate2 = num, count2 = 1;
else count1--, count2--;
}

count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
}

vector<int> result;
if (count1 > [Link]() / 3) result.push_back(candidate1);
if (count2 > [Link]() / 3) result.push_back(candidate2);
return result;
}

int main() {
vector<int> nums = {3,3,2,2,2,1,1,1,1};
vector<int> res = findMajorityElements(nums);
for (int num : res) cout << num << " ";
return 0;
}
// Output: 1 2

Java
import [Link].*;

public class MajorityElements {

public static List<Integer> findMajorityElements(int[] nums) {
int candidate1 = -1, candidate2 = -1, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
else if (count1 == 0) { candidate1 = num; count1 = 1; }
else if (count2 == 0) { candidate2 = num; count2 = 1; }
else { count1--; count2--; }
}
count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;

@the_DevXplained @the_dev_xplained
 ○​

else if (num == candidate2) count2++;

}
List<Integer> result = new ArrayList<>();
if (count1 > [Link] / 3) [Link](candidate1);
if (count2 > [Link] / 3) [Link](candidate2);
return result;
}
}
// Output: [1, 2]

10. Group words that are anagrams of each other in a dictionary

Algorithm:

1.​ Sort each word and use it as a key in a dictionary.

2.​ Group words having the same sorted key. Time Complexity: O(N * M log M) (M = max
length of a word) Space Complexity: O(NM)

Python
from collections import defaultdict

def group_anagrams(words):
anagrams = defaultdict(list)
for word in words:
anagrams[tuple(sorted(word))].append(word)
return list([Link]())

print(group_anagrams(["bat", "tab", "cat", "act", "tac"]))

# Output: [['bat', 'tab'], ['cat', 'act', 'tac']]

C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& words) {

unordered_map<string, vector<string>> map;
for (string word : words) {

@the_DevXplained @the_dev_xplained
 ○​

string sortedWord = word;

sort([Link](), [Link]());
map[sortedWord].push_back(word);
}
vector<vector<string>> result;
for (auto pair : map) result.push_back([Link]);
return result;
}

Java
import [Link].*;

public class GroupAnagrams {

public static List<List<String>> groupAnagrams(String[] words) {
Map<String, List<String>> anagramGroups = new HashMap<>();

for (String word : words) {

char[] charArray = [Link]();
[Link](charArray);
String sortedWord = new String(charArray);

[Link](sortedWord, new ArrayList<>());

[Link](sortedWord).add(word);
}

return new ArrayList<>([Link]());

}

public static void main(String[] args) {

String[] words = {"listen", "silent", "enlist", "eat", "tea", "ate", "bat", "tab"};
[Link](groupAnagrams(words));
}
}

11. Check if an array contains duplicate elements within k distance

Algorithm:

1.​ Use a sliding window approach with a hash set to track the last k elements.
2.​ If a duplicate is found within k distance, return True.
3.​ Otherwise, return False. Time Complexity: O(N) Space Complexity: O(k)

@the_DevXplained @the_dev_xplained
 ○​

Python
def contains_nearby_duplicate(nums, k):
seen = set()
for i, num in enumerate(nums):
if num in seen:
return True
[Link](num)
if len(seen) > k:
[Link](nums[i - k])
return False

C++
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) {

unordered_set<int> seen;
for (int i = 0; i < [Link](); i++) {
if ([Link](nums[i])) return true;
[Link](nums[i]);
if ([Link]() > k) [Link](nums[i - k]);
}
return false;
}

Java
import [Link].*;

public class DuplicateWithinK {

public static boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < [Link]; i++) {
if ([Link](nums[i])) return true;
[Link](nums[i]);
if ([Link]() > k) [Link](nums[i - k]);
}
return false;

@the_DevXplained @the_dev_xplained
 ○​

}
}

@the_DevXplained @the_dev_xplained