1.
Prefix Sum Array - Concept & Applications
🔹 Concept Recap:
A prefix sum array stores cumulative sums so you can answer range sum queries in O(1)
time after preprocessing.
2. Java Program: Range Sum using Prefix Sum Array
🔹 Java Code:
public class PrefixSumRange { .
public static int[] buildPrefixSum(int[] arr) {
int[] prefix = new int[arr.length];
prefix[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
return prefix;
}
public static int rangeSum(int[] prefix, int L, int R) {
if (L == 0) return prefix[R];
return prefix[R] - prefix[L - 1];
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int[] prefix = buildPrefixSum(arr);
System.out.println("Sum from index 1 to 3: " +
rangeSum(prefix, 1, 3)); // Output: 9
}
}
🔹 🔹Time Complexity: O(n) for prefix, O(1) per query
Space Complexity: O(n)
3. Java Program: Equilibrium Index
🔹 Java Code:
public class EquilibriumIndex {
public static int findEquilibrium(int[] arr) {
int total = 0;
for (int num : arr) total += num;
int leftSum = 0;
for (int i = 0; i < arr.length; i++) {
total -= arr[i]; // right sum
if (leftSum == total) return i;
leftSum += arr[i];
}
return -1;
}
public static void main(String[] args) {
int[] arr = {-7, 1, 5, 2, -4, 3, 0};
System.out.println("Equilibrium Index: " +
findEquilibrium(arr)); // Output: 3
}
}
🔹 Time Complexity: O(n)
🔹 Space Complexity: O(1)
4. Java Program: Check if Prefix Sum Equals Suffix Sum
🔹 Java Code:
public class PrefixEqualsSuffix {
public static boolean canBeSplit(int[] arr) {
int total = 0;
for (int num : arr) total += num;
int leftSum = 0;
for (int i = 0; i < arr.length; i++) {
total -= arr[i]; // right sum
if (leftSum == total) return true;
leftSum += arr[i];
}
return false;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 3};
System.out.println("Can be split: " + canBeSplit(arr)); //
Output: true
}
}
🔹 Time Complexity: O(n)
🔹 Space Complexity: O(1)
5. Java Program: Max Sum Subarray of Size K
🔹 Java Code:
public class MaxSubarraySumK {
public static int maxSumK(int[] arr, int k) {
if (arr.length < k) return -1;
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] arr = {2, 1, 5, 1, 3, 2};
int k = 3;
System.out.println("Max sum of subarray of size K: " +
maxSumK(arr, k)); // Output: 9
}
}
🔹 Time Complexity: O(n)
🔹 Space Complexity: O(1)
6. Longest Substring Without Repeating Characters
🔹 Java Code:
import java.util.HashSet; public
class LongestUniqueSubstring {
public static int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left++));
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
String str = "abcabcbb";
System.out.println("Length of Longest Unique Substring: " +
lengthOfLongestSubstring(str)); // 3
}
}
🔹 Time: O(n)
🔹 Space: O(k) (k = unique characters)
7. Sliding Window Technique (Explanation)
🔹 Concept:
A technique to solve problems involving contiguous subarrays or substrings using a
moving window.
🔹 How It Works:
• Maintain a window (usually of fixed or variable size).
• Move it forward while updating results based on constraints.
🔹 Used in:
• Maximum/minimum sum of size k
• Longest substring without repeating characters
• Counting distinct elements in a window
• Checking anagram existence in another string
8. Longest Palindromic Substring
🔹 Java Code:
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expand(s, i, i); // Odd
int len2 = expand(s, i, i + 1); // Even
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private static int expand(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) ==
s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
public static void main(String[] args) {
String str = "babad";
System.out.println("Longest Palindromic Substring: " +
longestPalindrome(str)); // "bab" or "aba"
}
}
🔹 Time: O(n^2)
🔹 Space: O(1)
9. Longest Common Prefix (LCP)
🔹 Java Code:
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " +
longestCommonPrefix(strs)); // "fl"
}
}
🔹 Time: O(n * m)
🔹 Space: O(1)
n = number of strings, m = length of smallest string
10. Generate All Permutations of a String
🔹 Java Code:
public class StringPermutations {
public static void permute(char[] arr, int l, int r) {
if (l == r) {
System.out.println(String.valueOf(arr));
} else {
for (int i = l; i <= r; i++) {
swap(arr, l, i);
permute(arr, l + 1, r);
swap(arr, l, i); // backtrack
}
}
}
private static void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
String str = "ABC";
permute(str.toCharArray(), 0, str.length() - 1);
}
}
🔹 Time: O(n * n!)
🔹 Space: O(n)
11. Two Numbers in a Sorted Array That Add Up to Target
🔹 Java Code:
public class TwoSumSorted {
public static int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 6};
int[] result = twoSum(arr, 6);
System.out.println("Indices: " + result[0] + ", " +
result[1]); // 1, 3
}
}
🔹 Time: O(n)
🔹 Space: O(1)
12. Next Lexicographical Permutation
🔹 Java Code:
import java.util.Arrays;
public class NextPermutation {
public static void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--;
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
}
private static void reverse(int[] nums, int start, int end) {
while (start < end) swap(nums, start++, end--);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
nextPermutation(nums);
System.out.println(Arrays.toString(nums)); // [1, 3, 2]
}
}
🔹 Time: O(n)
🔹 Space: O(1)
13. Merge Two Sorted Linked Lists
🔹 Java Code:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class MergeSortedLists {
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1), tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1; l1 = l1.next;
} else {
tail.next = l2; l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
🔹 🔹Time: O(n + m)
Space: O(1)
14. Median of Two Sorted Arrays
🔹 Java Code:
public class MedianSortedArrays {
public static double findMedianSortedArrays(int[] A, int[] B) {
if (A.length > B.length) return findMedianSortedArrays(B, A);
int m = A.length, n = B.length;
int low = 0, high = m;
while (low <= high) {
int i = (low + high) / 2;
int j = (m + n + 1) / 2 - i;
int maxLeftA = (i == 0) ? Integer.MIN_VALUE : A[i - 1];
int minRightA = (i == m) ? Integer.MAX_VALUE : A[i];
int maxLeftB = (j == 0) ? Integer.MIN_VALUE : B[j - 1];
int minRightB = (j == n) ? Integer.MAX_VALUE : B[j];
if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
if ((m + n) % 2 == 0)
return (Math.max(maxLeftA, maxLeftB) +
Math.min(minRightA, minRightB)) / 2.0;
else
return Math.max(maxLeftA, maxLeftB);
} else if (maxLeftA > minRightB)
high = i - 1;
else
low = i + 1;
}
return 0.0;
}
public static void main(String[] args) {
int[] A = {1, 3};
int[] B = {2};
System.out.println(findMedianSortedArrays(A, B)); // 2.0
}
}
🔹 Time: O(log(min(m,n)))
🔹 Space: O(1)
15. K-th Smallest in Sorted Matrix
🔹 Java Code:
public class KthSmallestSortedMatrix {
public static int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int low = matrix[0][0], high = matrix[n - 1][n - 1];
while (low < high) {
int mid = (low + high) / 2;
int count = 0, j = n - 1;
for (int i = 0; i < n; i++) {
while (j >= 0 && matrix[i][j] > mid) j--;
count += (j + 1);
}
if (count < k) low = mid + 1;
else high = mid;
return low;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 5, 9},
{10, 11, 13},
{12, 13, 15}
};
System.out.println(kthSmallest(matrix, 8)); // 13
}
}
🔹 Time: O(n log(max-min))
🔹 Space: O(1)
16. Majority Element (> n/2 times)
🔹 Java Code:
public class MajorityElement {
public static int findMajority(int[] nums) {
int count = 0, candidate = 0;
for (int num : nums) {
if (count == 0) candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
public static void main(String[] args) {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
System.out.println("Majority Element: " + findMajority(nums));
// 2
}
}
🔹 🔹Time: O(n)
Space: O(1)
17. Trapping Rain Water
🔹 Java Code:
public class TrappingRainWater {
public static int trap(int[] height) {
int left = 0, right = height.length - 1, res = 0;
int leftMax = 0, rightMax = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) leftMax = height[left];
else res += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax) rightMax =
height[right];
else res += rightMax - height[right];
right--;
}
}
return res;
}
public static void main(String[] args) {
int[] height = {0, 1, 0, 2, 1, 0, 1, 3};
System.out.println("Trapped Water: " + trap(height)); // 6
}
}
🔹 Time: O(n)
🔹 Space: O(1)
18. Maximum XOR of Two Numbers in Array
🔹 Java Code:
import
java.util.HashSet;
public class MaxXOR {
public static int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for (int i = 31; i >= 0; i--) {
mask |= (1 << i);
HashSet<Integer> set = new HashSet<>();
for (int num : nums) set.add(num & mask);
int temp = max | (1 << i);
for (int prefix : set) {
if (set.contains(temp ^ prefix)) {
max = temp;
break;
}
}
}
return max;
}
public static void main(String[] args) {
int[] nums = {3, 10, 5, 25, 2, 8};
System.out.println("Max XOR: " + findMaximumXOR(nums)); // 28
}
}
🔹 Time: O(n)
🔹 Space: O(n)
19. Maximum Product Subarray
🔹 Java Code:
public class MaxProductSubarray {
public static int maxProduct(int[] nums) {
int max = nums[0], min = nums[0], result = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = max;
max = Math.max(nums[i], Math.max(max * nums[i], min *
nums[i]));
min = Math.min(nums[i], Math.min(temp * nums[i], min *
nums[i]));
result = Math.max(result, max);
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 3, -2, 4};
System.out.println("Max Product: " + maxProduct(nums)); // 6
}
}
Time: O(n)
Space: O(1)
20. Count All Numbers with Unique Digits
🔹 Java Code:
public class UniqueDigitNumbers {
public static int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
int res = 10, uniqueDigits = 9, available = 9;
for (int i = 2; i <= n && available > 0; i++) {
uniqueDigits *= available;
res += uniqueDigits;
available--;
}
return res;
}
public static void main(String[] args) {
System.out.println(countNumbersWithUniqueDigits(2)); // 91
}
}
🔹 Time: O(n)
🔹 Space: O(1)
21. Count 1s in Binary Representations from 0 to n
,
Java Code:
public int[] countBits(int n) {
int[] res = new int[n + 1]; for
(int i = 1; i <= n; i++) {
res[i] = res[i >> 1] + (i & 1);
}
return res;
}
Time Complexity: O(n)
Space Complexity: O(n)
Example: n = 5 → Output: [0,1,1,2,1,2]
22. Check Power of Two using Bit Manipulation
Code: .
public boolean isPowerOfTwo(int n)
{
return n > 0 && (n & (n - 1)) == 0;
Time Complexity: O(1)
Space Complexity: O(1)
Example: n = 8 → Output: true
23. Maximum XOR of Two Numbers in Array
Java Code:
class TrieNode {
TrieNode[] child = new TrieNode[2];
}
public int findMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
TrieNode node = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.child[bit] == null)
node.child[bit] = new TrieNode();
node = node.child[bit];
}
}
int maxXOR = 0;
for (int num : nums) {
TrieNode node = root;
int currXOR = 0;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (node.child[bit ^ 1] != null) {
currXOR |= (1 << i);
node = node.child[bit ^ 1];
} else {
node = node.child[bit];
}
}
m a x X O R = M a t h . m a x ( m a x X O R , c u r r X
} }
return maxXOR;
Time Complexity: O(n * 32)
Space Complexity: O(n * 32)
Example: [3, 10, 5, 25, 2, 8] → Output: 28
24. Bit Manipulation Concept
Explanation: Bit manipulation deals with bitwise operations (AND, OR, XOR, NOT, shift). It is
efficient in time and memory, widely used in low-level programming, optimization, and
competitive coding.
Advantages:
• Constant-time operations
• Efficient data compression
• Can solve tricky problems with elegance (e.g., XOR to find duplicates)
25. Next Greater Element in Array
Java Code:
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[nums.length];
Arrays.fill(res, -1);
for (int i = 0; i < nums.length * 2; i++) {
int num = nums[i % nums.length];
while (!stack.isEmpty() && nums[stack.peek()] < num)
res[stack.pop()] = num;
if (i < nums.length)
stack.push(i);
}
return res;
}
Time Complexity: O(n)
Space Complexity: O(n)
Example: [2,1,2,4,3] → Output: [4,2,4,-1,-1]
26. Remove N-th Node from End of List
Java Code: n
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy, second = dummy;
for (int i = 0; i <= n; i++) first = first.next;
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
Time Complexity: O(n)
Space Complexity: O(1)
Example: [1,2,3,4,5], n=2 → Output: [1,2,3,5]
27. Intersection of Two Linked Lists
Java Code:
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
{
ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
} }
return a;
Time Complexity: O(m + n)
Space Complexity: O(1)
Example: List A: [4,1,8,4,5], B: [5,6,1,8,4,5] → Output: 8
28. Implement Two Stacks in One Array
Java Code:
class TwoStacks {
int[] arr;
int top1, top2;
TwoStacks(int size) {
arr = new int[size];
top1 = -1;
top2 = size;
}
void push1(int x) {
if (top1 + 1 < top2)
arr[++top1] = x;
}
void push2(int x) {
if (top1 + 1 < top2)
arr[--top2] = x;
}
int pop1() {
return top1 >= 0 ? arr[top1--] : -1;
}
int pop2() {
return top2 < arr.length ? arr[top2++] : -1;
} }
Time Complexity: O(1)
Space Complexity: O(n)
Example: Push elements in two stacks from same array.
29. Check Palindrome Integer Without String
Java Code:
public boolean isPalindrome(int x)
{
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev) {
rev = rev * 10 + x % 10;
x /= 10;
}
} r e t u r n x = = r e v | | x = = r e v / 1 0
Time Complexity: O(log n)
Space Complexity: O(1)
Example: 121 → Output: true
30. Linked List Concept and Applications
Explanation: A linked list is a linear data structure where elements (nodes) point to the
next. Types include singly, doubly, and circular linked lists.
Applications:
• Implementing stacks and queues
• Dynamic memory allocation
• Polynomial manipulation
• Adjacency representation in graphs
31. Maximum in Every Sliding Window of Size K (Deque Approach)
Java Code:
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n - k + 1];
for (int i = 0; i < n; i++) {
if (!deque.isEmpty() && deque.peek() == i - k)
deque.poll();
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
deque.pollLast();
deque.offer(i);
if (i >= k - 1)
res[i - k + 1] = nums[deque.peek()];
}
return res;
}
Time Complexity: O(n)
Space Complexity: O(k)
Example: [1,3,-1,-3,5,3,6,7], k=3 → Output: [3,3,5,5,6,7]
32. Largest Rectangle in Histogram
Java Code:
public int largestRectangleArea(int[] heights)
{
Stack<Integer> stack = new Stack<>();
int maxArea = 0, i = 0;
while (i < heights.length) {
if (stack.isEmpty() || heights[i] >= heights[stack.peek()])
stack.push(i++);
else {
int h = heights[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, h * w);
}
}
while (!stack.isEmpty()) {
int h = heights[stack.pop()];
int w = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, h * w);
}
return maxArea;
}
Time Complexity: O(n)
Space Complexity: O(n)
Example: [2,1,5,6,2,3] → Output: 10
33. Sliding Window Technique (Explanation)
Concept: Efficiently process subsets of data using a fixed-size or variable-size window,
avoiding recomputation.
Use Cases:
• Maximum/Minimum in window
• Longest substring without repeating characters
• Average of subarrays
34. Subarray Sum Equals K (Hashing)
Code:
public int subarraySum(int[] nums, int k)
{
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
Time Complexity: O(n)
Space Complexity: O(n)
Example: [1,2,3], k=3 → Output: 2
35. K Most Frequent Elements (Priority Queue)
Java Code:
public int[] topKFrequent(int[] nums, int k)
{
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums)
map.put(n, map.getOrDefault(n, 0) + 1);
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> map.get(a) - map.get(b)
);
for (int key : map.keySet()) {
pq.offer(key);
if (pq.size() > k)
pq.poll();
}
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--)
res[i] = pq.poll();
return res;
}
Time Complexity: O(n log k)
Space Complexity: O(n)
Example: [1,1,1,2,2,3], k=2 → Output: [1,2]
36. Generate All Subsets (Power Set)
Backtracking):
public List<List<Integer>> subsets(int[] nums)
{ List<List<Integer>> res = new ArrayList<>();
backtrack(res, new ArrayList<>(), nums, 0);
return res;
}
private void backtrack(List<List<Integer>> res, List<Integer> temp,
int[] nums, int start) {
res.add(new ArrayList<>(temp));
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
backtrack(res, temp, nums, i + 1);
temp.remove(temp.size() - 1);
}
}
Time Complexity: O(2^n)
Space Complexity: O(2^n)
Example: [1,2] → Output: [[],[1],[2],[1,2]]
37. Unique Combinations That Sum to Target
Java Code:
public List<List<Integer>> combinationSum(int[] candidates, int
target) {
List<List<Integer>> res = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), res);
} return res;
private void backtrack(int[] candidates, int target, int start,
List<Integer> temp, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] > target) continue;
temp.add(candidates[i]);
backtrack(candidates, target - candidates[i], i, temp, res);
temp.remove(temp.size() - 1);
}
}
Time Complexity: O(2^t), where t = target
Space Complexity: O(target)
Example: candidates = [2,3,6,7], target = 7 → Output: [[2,2,3],[7]]
38. Permutations of an Array
Java Code:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, res);
return res;
}
private void backtrack(int[] nums, int start, List<List<Integer>> res)
{
if (start == nums.length) {
List<Integer> temp = new ArrayList<>();
for (int num : nums) temp.add(num);
res.add(temp);
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, i, start);
backtrack(nums, start + 1, res);
swap(nums, i, start);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Time Complexity: O(n!)
Space Complexity: O(n)
Example: [1,2] → Output: [[1,2],[2,1]]
39. Difference Between Subsets and Permutations
Explanation:
• Subsets: Any combination of elements, order doesn’t matter. Example: {1, 2} →
{1}, {2}, {1, 2}, {}
• Permutations: All possible arrangements, order matters. Example: {1, 2} →
[1,2], [2,1]
Key Differences:
• Count of subsets: 2^n
• Count of permutations: n!
40. Element with Maximum Frequency in Array
Java Code:
public int maxFrequencyElement(int[] nums)
{
Map<Integer, Integer> map = new HashMap<>();
int maxFreq = 0, element = nums[0];
for (int num : nums) {
int freq = map.getOrDefault(num, 0) + 1;
map.put(num, freq);
if (freq > maxFreq) {
maxFreq = freq;
element = num;
}
}
return element;
}
Time Complexity: O(n)
Space Complexity: O(n)
Example: [1,3,2,2,3,1,1] → Output: 1
41. Maximum Subarray Sum (Kadane’s Algorithm)
Java Code:
public int maxSubArray(int[] nums) {
int maxSoFar = nums[0], maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
Time: O(n)
Space: O(1)
Example: [-2,1,-3,4,-1,2,1,-5,4] → 6
42. Dynamic Programming in Maximum Subarray
Concept:
Use DP to store max sum ending at each index.
DP Relation:
dp[i] = max(nums[i], dp[i-1] + nums[i])
Java Code:
java
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
max = Math.max(max, dp[i]);
}
return max;
}
Time: O(n)
Space: O(n)
43. Top K Frequent Elements
Java Code:
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums)
map.put(n, map.getOrDefault(n, 0) + 1);
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> map.get(a) - map.get(b)
);
for (int key : map.keySet()) {
pq.add(key);
if (pq.size() > k)
pq.poll();
}
int[] result = new int[k];
for (int i = 0; i < k; i++)
result[i] = pq.poll();
return result;
}
Time: O(n log k)
Space: O(n)
44. Two Numbers Add to Target (Hashing)
Java Code:
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement))
return new int[]{map.get(complement), i};
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
Time: O(n)
Space: O(n)
45. Priority Queue Concept
Explanation:
• A PriorityQueue is a heap-based data structure.
• Elements are ordered based on natural ordering or custom
comparator.
• Use Cases: Dijkstra's algorithm, Top-K problems, job scheduling.
46. Longest Palindromic Substring
Java Code:
public String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandFromCenter(s, i, i);
int len2 = expandFromCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandFromCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) ==
s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
Time: O(n²)
Space: O(1)
47. Histogram Problem Concept
Concept:
• Largest rectangle under histogram bars.
• Applications: Max area in binary matrix, skyline problem.
• Techniques: Stack, Divide & Conquer.
48. Next Permutation
Java Code:
java
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--;
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end)
swap(nums, start++, end--);
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp;
}
Time: O(n)
Space: O(1)
49. Intersection of Two Linked Lists
Java Code:
java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
Time: O(m + n)
Space: O(1)
50. Equilibrium Index (Concept)
Definition:
An index i such that sum of elements before i equals sum after i.
Applications:
• Load balancing
• Stock span analysis
• Partition-based problems
Approach:
Use total sum and subtract prefix while iterating.
