Single Number (leetcode 136)

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

class Solution {
    public int singleNumber(int[] nums) {
        int r=0;
        for(var i:nums){
            r^=i;
        }
        return r;

    }
}

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        r = 0
        for num in nums:
            r ^= num
        return r

Type	Value
Time	O(n)
Space	O(1)

• Approach: XOR operation. a ^ a = 0 and a ^ 0 = a. XORing all numbers leaves the unique one.
• Dry run (nums = [4,1,2,1,2]):
  • r = 0 ^ 4 = 4
  • r = 4 ^ 1 = 5
  • r = 5 ^ 2 = 7
  • r = 7 ^ 1 = 6
  • r = 6 ^ 2 = 4 → Answer is 4.

---

Contains Duplicate (LeetCode 217)

217. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

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

Output: true

Explanation:

The element 1 occurs at the indices 0 and 3.

Example 2:

Input: nums = [1,2,3,4]

Output: false

Explanation:

All elements are distinct.

import java.util.*;
class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n)) {
                return true;
            }
            set.add(n);
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(nums) != len(set(nums))

Type	Value
Time	O(n)
Space	O(n)

• Approach: Add all elements to a Set and verify if sizes change.
• Dry run (nums=[1,2,3,1]):
  • Set length is 3, nums length is 4. -> true.

---

Missing Number (leetcode 268)

268. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

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

Explanation:
n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2

Explanation:
n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Explanation:
n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

Type	Value
Time	O(n)
Space	O(1)

• Approach: Calculate expected sum of 1 to n using formula n * (n + 1) / 2, subtract actual sum to find missing number.
• Dry run (nums = [3,0,1], n=3):
  • Expected sum = 3 * 4 / 2 = 6
  • Actual sum = 3 + 0 + 1 = 4
  • Missing number = 6 - 4 = 2.

---

Can Place Flowers (leetcode 605)

605. Can Place Flowers

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: false

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int len=flowerbed.length;
        for(int i=0;i<len;i+=2){
            if(flowerbed[i]==0){
                if(i==len-1 || flowerbed[i]==flowerbed[i+1]){
                    n--;
                }
                else{
                    i++;
                }
            }
        }
        return n<=0;
    }
}

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        length = len(flowerbed)
        i = 0
        while i < length:
            if flowerbed[i] == 0:
                if i == length - 1 or flowerbed[i] == flowerbed[i+1]:
                    n -= 1
                else:
                    i += 1
            i += 2
        return n <= 0

Type	Value
Time	O(n)
Space	O(1)

• Approach: Iterate through the flowerbed. Place a flower if the current plot is empty and its neighbors are also empty. Count the number of flowers placed.
• Dry run (flowerbed = [1,0,0,0,1], n=1):
  • i=0: flowerbed[0]=1, not 0 → skip. (i becomes 2 via i+=2)
  • i=2: flowerbed[2]=0. i==len-1? No. flowerbed[2]==flowerbed[3]? 0==0 → Yes → n-- → n=0. (i becomes 4 via i+=2)
  • i=4: flowerbed[4]=1, not 0 → skip. (i becomes 6, loop ends since 6 >= 5)
  • n=0 ≤ 0 → return true.

---

How Many Numbers Are Smaller Than the Current Number (LeetCode 1365)

1365. How Many Numbers Are Smaller Than the Current Number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] count = new int[101];
        for (int num : nums) {
            count[num]++;
        }
        for (int i = 1; i < 101; i++) {
            count[i] += count[i - 1];
        }
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                result[i] = 0;
            } else {
                result[i] = count[nums[i] - 1];
            }
        }
        return result;
    }
}

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        count = [0] * 101
        for num in nums: count[num] += 1
        for i in range(1, 101): count[i] += count[i-1]
        return [count[num-1] if num > 0 else 0 for num in nums]

Type	Value
Time	O(n)
Space	O(1) (fixed size array)

• Approach: Count sort. Maintain frequency of each element and precompute prefix sums.
• Dry run (nums=[8,1,2,2,3]):
  • freq counts and prefix computed.
  • Return previous prefix sum for each num.

---

Frequency Count (GeeksforGeeks)

Frequencies of Limited Range Array Elements

Given an array, output the frequency of each element.

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

import java.util.*;

class Solution {
    public ArrayList<ArrayList<Integer>> frequencyCount(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int key : map.keySet()) {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(key);
            temp.add(map.get(key));
            res.add(temp);
        }
        return res;
    }
}

class Solution:
    def frequencyCount(self, arr: List[int]) -> List[List[int]]:
        from collections import defaultdict
        freq_map = defaultdict(int)
        for num in arr:
            freq_map[num] += 1

        res = []
        for key, value in freq_map.items():
            res.append([key, value])
        return res

Type	Value
Time	O(n)
Space	O(n)

• Approach: Use a HashMap to count occurrences and then convert to a list of lists.
• Dry run (arr=[1,2,1,3]):
  • map: {1:2, 2:1, 3:1}
  • res: [[1,2], [2,1], [3,1]]

---

Replace with Index (GeeksforGeeks)

You are given a list of N unique positive numbers ranging from 0 to (N -1). Write an algorithm to replace the value of each number with its corresponding index value in the list.

Example 1:
Input: number = [1,3,0,2]
Output: [2,0,3,1]

public class Solution {
    public static int[] replaceWithIndex(int[] arr) {
        int n = arr.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[arr[i]] = i;
        }
        return res;
    }
}

class Solution:
    def replaceWithIndex(self, arr: List[int]) -> List[int]:
        n = len(arr)
        res = [0] * n
        for i in range(n):
            res[arr[i]] = i
        return res

Type	Value
Time	O(n)
Space	O(n)

• Approach: Create a result array, and use the value of the current element as the index for the new array.
• Dry run (arr = [1,3,0,2]):
  • i=0, arr[0]=1, res[1]=0
  • i=1, arr[1]=3, res[3]=1
  • i=2, arr[2]=0, res[0]=2
  • i=3, arr[3]=2, res[2]=3
  • Result: [2,0,3,1]

---

Distribute Candies (leetcode 575)

575. Distribute Candies

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor. The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

import java.util.HashSet;

class Solution {
    public int distributeCandies(int[] candyType) {
        HashSet<Integer> set = new HashSet<>();
        for (int c : candyType) {
            set.add(c);
        }
        int uniqueTypes = set.size();
        int canEat = candyType.length / 2;
        return Math.min(uniqueTypes, canEat);
    }
}

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        unique_types = len(set(candyType))
        can_eat = len(candyType) // 2
        return min(unique_types, can_eat)

Type	Value
Time	O(n)
Space	O(n)

• Approach: Use a HashSet to count unique candy types and return the minimum of unique types or n/2.
• Dry run (candyType = [1,1,2,3]):
  • n = 4, canEat = 2
  • set = {1, 2, 3}, uniqueTypes = 3
  • Math.min(3, 2) → Answer is 2.

---

Largest Perimeter Triangle (LeetCode 976)

976. Largest Perimeter Triangle

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

Input: nums = [2,1,2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.
Example 2:

Input: nums = [1,2,1,10]
Output: 0
Explanation:
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

import java.util.*;
class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 2; i--) {
            if (nums[i - 1] + nums[i - 2] > nums[i]) {
                return nums[i - 1] + nums[i - 2] + nums[i];
            }
        }
        return 0;
    }
}

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        for i in range(len(nums) - 2):
            if nums[i+1] + nums[i+2] > nums[i]:
                return nums[i] + nums[i+1] + nums[i+2]
        return 0

Type	Value
Time	O(n log n)
Space	O(1)

• Approach: Sort; check triangle inequality from largest side.
• Dry run (nums=[2,1,2]): sort→[1,2,2], check 2+1>2 → true → perimeter=5

---

Remove Duplicates from Sorted Array (LeetCode 26)

26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Consider the number of unique elements in nums to be k. After removing duplicates, return the number of unique elements k.

The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k - 1 can be ignored.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1])
                nums[j++] = nums[i];
        }
        return j;
    }
}

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        j = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[j] = nums[i]
                j += 1
        return j

Type	Value
Time	O(n)
Space	O(1)

• Approach: Two pointers; write unique elements forward.
• Dry run (nums = [1,1,2]):
  • j=1
  • i=1: nums[1]=1 == nums[0]=1 → skip
  • i=2: nums[2]=2 != nums[1]=1 → nums[1]=2, j=2
  • Result length=2; array becomes [1,2,_]

---

Merge Sorted Array (leetcode 88)

88. Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = n + m - 1;
        while (j >= 0) {
            if (i < 0) {
                nums1[k--] = nums2[j--];
            } else if (nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

Type	Value
Time	O(m+n)
Space	O(1)

• Approach: Use three pointers starting from the end. i points to the last real element in nums1, j points to the last element in nums2, and k points to the last position in nums1. Compare elements from the ends of both arrays and place the larger one at position k, moving backwards. This avoids overwriting elements that haven't been processed yet.
• Dry run (nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3):
  • i=2, j=2, k=5: nums1[2]=3 < nums2[2]=6 → nums1[5]=6, j=1, k=4. nums1=[1,2,3,0,0,6]
  • i=2, j=1, k=4: nums1[2]=3 < nums2[1]=5 → nums1[4]=5, j=0, k=3. nums1=[1,2,3,0,5,6]
  • i=2, j=0, k=3: nums1[2]=3 >= nums2[0]=2 → nums1[3]=3, i=1, k=2. nums1=[1,2,3,3,5,6]
  • i=1, j=0, k=2: nums1[1]=2 >= nums2[0]=2 → nums1[2]=2, i=0, k=1. nums1=[1,2,2,3,5,6]
  • i=0, j=0, k=1: nums1[0]=1 < nums2[0]=2 → nums1[1]=2, j=-1, k=0. nums1=[1,2,2,3,5,6]
  • j < 0, loop ends. Result: [1,2,2,3,5,6]

---

Move Zeroes (LeetCode 283)

283. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

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

Input: nums = [0]
Output: [0]

class Solution {
    public void moveZeroes(int[] nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[insertPos++] = num;
            }
        }
        while (insertPos < nums.length) {
            nums[insertPos++] = 0;
        }
    }
}

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        insert_pos = 0
        for num in nums:
            if num != 0:
                nums[insert_pos] = num
                insert_pos += 1
        for i in range(insert_pos, len(nums)):
            nums[i] = 0

Type	Value
Time	O(n)
Space	O(1)

• Approach: Compact non-zeros then fill the rest with zeros.
• Dry run (nums=[0,1,0,3,12]):
  • First pass writes 1,3,12 to positions 0..2 → insertPos=3
  • Fill positions 3..4 with 0 → [1,3,12,0,0]

---

Plus One (LeetCode 66)

66. Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
        return [1] + digits

Type	Value
Time	O(n)
Space	O(n)

• Approach: Increment from end; handle carry-overflow.
• Dry run 1 (digits=[1,2,3]): i=2 → 3<9 → set 4 and return [1,2,4]
• Dry run 2 (digits=[9,9,9]): i=2→0, i=1→0, i=0→0 → new array [1,0,0,0]

---

Wave Array (GeeksforGeeks)

Wave Array

Given an unsorted array, sort it in wave form. An array arr[0..n-1] is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ….

Example:

Input: arr = [1, 2, 3, 4, 5, 6]
Output: [2, 1, 4, 3, 6, 5]

public class Main {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 5, 6};

        for (int i = 0; i < arr.length; i += 2) {
            if (i > 0 && arr[i - 1] > arr[i]) {
                swap(arr, i, i - 1);
            }
            if (i < arr.length - 1 && arr[i + 1] > arr[i]) {
                swap(arr, i, i + 1);
            }
        }

        System.out.println("Wave Array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

def wave_array(arr):
    n = len(arr)
    for i in range(0, n, 2):
        if i > 0 and arr[i - 1] > arr[i]:
            arr[i], arr[i - 1] = arr[i - 1], arr[i]
        if i < n - 1 and arr[i + 1] > arr[i]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return arr

Type	Value
Time	O(n)
Space	O(1)

• Approach: Iterate through even indices. At each even index, ensure the element is greater than or equal to its neighbors by swapping if needed.

• Dry run (arr = [1,2,3,4,5,6]):

  • i=0: right neighbor 2 > 1 → swap → [2,1,3,4,5,6]
  • i=2: right neighbor 4 > 3 → swap → [2,1,4,3,5,6]
  • i=4: right neighbor 6 > 5 → swap → [2,1,4,3,6,5]
  • Result: [2,1,4,3,6,5]

  ---

135. Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

class Solution {
    public int candy(int[] ratings) {

        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        int total = 0;
        for (int candy : candies) {
            total += candy;
        }
        return total;
    }
}

---

Two Sum II - Input Array Is Sorted (LeetCode 167)

167. Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return new int[]{l + 1, r + 1};
            else if (sum < target) l++;
            else r--;
        }
        return new int[]{};
    }
}

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left + 1, right + 1]  
            elif s < target:
                left += 1
            else:
                right -= 1

Type	Value
Time	O(n)
Space	O(1)

• Approach: Use two pointers at ends, increment left if sum is too small or right if too large.
• Dry run (nums=[2,7,11,15], target=9):
  • left=2, right=15 -> 17 > 9 -> r--
  • left=2, right=11 -> 13 > 9 -> r--
  • left=2, right=7 -> 9 == 9 -> return [1,2].

---

Remove Duplicates from Sorted Array II (LeetCode 80)

80. Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,,]

class Solution {

    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int num : nums) {
            if (i < 2 || nums[i - 2] != num) {
                nums[i] = num;
                i++;
            }
        }
        return i;
    }
}

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for num in nums:
            if i < 2 or nums[i - 2] != num:
                nums[i] = num
                i += 1
        return i

Type	Value
Time	O(n)
Space	O(1)

• Approach: Keep a placement pointer i checking if current num is different from nums[i-2].
• Dry run (nums=[1,1,1,2,2,3]):
  • i=0, num=1 -> nums[0]=1, i=1
  • i=1, num=1 -> nums[1]=1, i=2
  • i=2, num=1 -> 1 == nums[0], skip
  • i=2, num=2 -> nums[2]=2, i=3
  • Returns new length.

---

Sort Colors (LeetCode 75)

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library's sort function.

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

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

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

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low = 0
        mid = 0
        high = len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[mid], nums[low] = nums[low], nums[mid]
                mid += 1
                low += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

Type	Value
Time	O(n)
Space	O(1)

• Approach: Dutch National Flag algorithm using three pointers (low, mid, high). We partition the array such that elements from 0 to low-1 are 0s, from low to mid-1 are 1s, and from high+1 to n-1 are 2s.
• Dry run (nums = [2,0,2,1,1,0]):
  • low=0, mid=0, high=5.
  • nums[mid] == 2 -> swap nums[mid] and nums[high], high=4. nums = [0,0,2,1,1,2]
  • nums[mid] == 0 -> swap nums[mid] and nums[low], mid=1, low=1. nums = [0,0,2,1,1,2]
  • nums[mid] == 0 -> swap nums[mid] and nums[low], mid=2, low=2. nums = [0,0,2,1,1,2]
  • nums[mid] == 2 -> swap nums[mid] and nums[high], high=3. nums = [0,0,1,1,2,2]
  • nums[mid] == 1 -> mid=3.
  • nums[mid] == 1 -> mid=4. mid > high (4 > 3) -> loop ends.

---

Rearrange Array Elements by Sign (LeetCode 2149)

2149. Rearrange Array Elements by Sign

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should return the array of nums such that the array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.
Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int[] arr = new int[nums.length];
        int positiveIdx = 0, negativeIdx = 1;
        for (int n : nums) {
            if (n >= 0) {
                arr[positiveIdx] = n;
                positiveIdx += 2;
            } else {
                arr[negativeIdx] = n;
                negativeIdx += 2;
            }
        }
        return arr;
    }
}

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        arr = [0] * len(nums)
        pos_idx, neg_idx = 0, 1
        for n in nums:
            if n > 0:
                arr[pos_idx] = n
                pos_idx += 2
            else:
                arr[neg_idx] = n
                neg_idx += 2
        return arr

Type	Value
Time	O(n)
Space	O(n)

• Approach: Place positives at even indices (0,2,4,...) and negatives at odd indices (1,3,5,...) while preserving relative order.
• Dry run (nums = [3,1,-2,-5,2,-4]):
  • Start arr=[,,,,,], positiveIdx=0, negativeIdx=1
  • n=3 -> arr[0]=3, positiveIdx=2
  • n=1 -> arr[2]=1, positiveIdx=4
  • n=-2 -> arr[1]=-2, negativeIdx=3
  • n=-5 -> arr[3]=-5, negativeIdx=5
  • n=2 -> arr[4]=2, positiveIdx=6
  • n=-4 -> arr[5]=-4, negativeIdx=7
  • Result: [3,-2,1,-5,2,-4]

---

Two Sum (LeetCode 1)

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (map.containsKey(diff))
                return new int[]{map.get(diff), i};
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in hash_map:
                return [hash_map[diff], i]
            hash_map[num] = i
        return []

Type	Value
Time	O(n)
Space	O(n)

• Approach: Use a HashMap to store seen values and check for complement in O(n).
• Dry run (nums = [2,7,11,15], target = 9):
  • i=0, num=2, diff=7, map={}, not found → put 2:0
  • i=1, num=7, diff=2, map has 2 → return [0,1]

---

Find Pairs with Sum 0 (GeeksforGeeks)

Find Pairs with Sum 0

Example 1:

Input: arr = [1, -1, 2, -2, 3, -3, 1]
Output: [[-3, 3], [-2, 2], [-1, 1]]

import java.util.*;
class Solution {
    public List<List<Integer>> findPairs(int[] arr) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(arr);
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == 0) {
                res.add(Arrays.asList(arr[left], arr[right]));
                int lVal = arr[left];
                int rVal = arr[right];
                while (left < right && arr[left] == lVal) left++;
                while (left < right && arr[right] == rVal) right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        int[] arr = {1, -1, 2, -2, 3, -3, 1};

        List<List<Integer>> ans = sol.findPairs(arr);

        for (List<Integer> pair : ans) {
            System.out.println(pair);
        }
    }
}

class Solution:
    def findPairs(self, arr):
        res = []
        arr.sort()
        left, right = 0, len(arr) - 1

        while left < right:
            current_sum = arr[left] + arr[right]
            if current_sum == 0:
                res.append([arr[left], arr[right]])
                l_val, r_val = arr[left], arr[right]
                while left < right and arr[left] == l_val:
                    left += 1
                while left < right and arr[right] == r_val:
                    right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
        return res

Type	Value
Time	O(n log n)
Space	O(1)

• Approach: Sort the array first. Use two pointers to find pairs that sum to 0. Skip duplicates to avoid repeated pairs.
• Dry run (arr = [1, -1, 2, -2, 3, -3, 1]):
  • Sort → [-3,-2,-1,1,1,2,3]
  • left=0, right=6. sum=-3+3=0 → found [-3,3]. Skip dups. left=1, right=5. sum=-2+2=0 → found [-2,2]. Skip dups. left=2, right=4. sum=-1+1=0 → found [-1,1]. Skip dups. left=3, right=3. stop.
  • Result: [[-3,3], [-2,2], [-1,1]]

---

3Sum (LeetCode 15)

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1])
                        l++;
                    while (l < r && nums[r] == nums[r - 1])
                        r--;
                    l++;
                    r--;
                } else if (sum < 0)
                    l++;
                else
                    r--;
            }
        }
        return res;
    }
}

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
        return res

Type	Value
Time	O(n²)
Space	O(1) (excluding output)

• Approach: Sort the array first. Fix one element with index i, then use two pointers (l and r) to find pairs that sum to -nums[i]. Skip duplicates at all three levels to avoid repeated triplets.
• Dry run (nums = [-1,0,1,2,-1,-4]):
  • Sort → [-4,-1,-1,0,1,2]
  • i=0, nums[i]=-4: l=1, r=5. sum=-4+(-1)+2=-3 < 0 → l++. sum=-4+(-1)+2=-3 < 0 → l++. sum=-4+0+2=-2 < 0 → l++. sum=-4+1+2=-1 < 0 → l++. l >= r, stop.
  • i=1, nums[i]=-1: l=2, r=5. sum=-1+(-1)+2=0 → found [-1,-1,2]. Skip dups. l=3, r=4. sum=-1+0+1=0 → found [-1,0,1]. Skip dups. l=4, r=3, stop.
  • i=2, nums[i]=-1: same as nums[1], skip duplicate.
  • i=3, nums[i]=0: l=4, r=5. sum=0+1+2=3 > 0 → r--. l >= r, stop.
  • Result: [[-1,-1,2], [-1,0,1]]

---

Container With Most Water (Leetcode 11)

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.
Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49
Explanation: The max area of water the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

class Solution {
    public int maxArea(int[] h) {
        int left = 0;
        int right = h.length - 1;
        int mx = 0;
        while (left < right) {
            int hi = Math.min(h[left], h[right]);
            int w = right - left;
            mx = Math.max(mx, hi * w);
            if (h[left] < h[right]) {
                left++;
            } else {
                right--;
            }
        }
        return mx;
    }
}

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        mx = 0
        while left < right:
            hi = min(height[left], height[right])
            w = right - left
            mx = max(mx, hi * w)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return mx

Type	Value
Time	O(n)
Space	O(1)

• Approach: Two pointers strategy (left and right). At each step, calculate the area and move the pointer that points to the shorter line, trying to find a taller line to maximize the area.
• Dry run (height = [1,8,6,2,5,4,8,3,7]):
  • left=0 (val 1), right=8 (val 7) → w=8, h=1, area=8, max=8. Move left.
  • left=1 (val 8), right=8 (val 7) → w=7, h=7, area=49, max=49. Move right.
  • Continues until pointers meet... returns max area 49.

---

Trapping Rain Water (LeetCode 42)

42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

class Solution {

    public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int max = -1;
        for(int i = 0;i<height.length;i++)
        {
           if(height[i] >= max )
           {
              max = height[i];
           }
            left[i] = max;
        }
        max = -1;
        for(int i = height.length - 1;i>=0;i--)
        {
           if(height[i] >= max )
           {
              max = height[i];
           }
            right[i] = max;
        }
        int total = 0;
        for(int i =0;i<height.length;i++)
        {
            total += Math.min(left[i],right[i]) - height[i];
        }
        return total;

    }
}

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0: return 0
        left = [0] * n
        right = [0] * n

        max_val = -1
        for i in range(n):
            if height[i] >= max_val:
                max_val = height[i]
            left[i] = max_val

        max_val = -1
        for i in range(n - 1, -1, -1):
            if height[i] >= max_val:
                max_val = height[i]
            right[i] = max_val

        total = 0
        for i in range(n):
            total += min(left[i], right[i]) - height[i]
        return total

Type	Value
Time	O(n)
Space	O(n)

• Approach: Precompute arrays for the maximum height to the left and to the right of every index. The water trapped at any index is the minimum of leftMax and rightMax minus the height at that index.
• Dry run (height = [0,1,0,2,1,0,1,3,2,1,2,1]):
  • left = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
  • right = [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]
  • min arrays = [0, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 1]
  • Using difference: total = +0 +0 +1 +0 +1 +2 +1 +0 +0 +1 +0 +0 = 6
  • Returns 6.

---

Equilibrium Point (GeeksforGeeks)

Equilibrium Point

Given an array arr, find the first index where the sum of elements on its left equals the sum on its right. Return -1 if no such index exists.

Example 1:

Input: arr = [1,7,3,6,5,6]
Output: 3
Explanation: Left sum = 1+7+3 = 11, Right sum = 5+6 = 11.

Example 2:

Input: arr = [1,2,3]
Output: -1
Explanation: No index has equal left and right sums.

class Main {
    static int equilibriumPoint(int[] arr) {
        int prefSum = 0, total = 0;

        // Calculate the array sum
        for (int ele : arr) {
            total += ele;
        }

        for (int pivot = 0; pivot < arr.length; pivot++) {
            int suffSum = total - prefSum - arr[pivot];
            if (prefSum == suffSum) {
                return pivot;
            }
            prefSum += arr[pivot];
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 3, 6, 5, 6};

        System.out.println(equilibriumPoint(arr));
    }
}

class Solution:
    def equilibriumPoint(self, arr):
        total = sum(arr)
        pref_sum = 0

        for pivot, num in enumerate(arr):
            suff_sum = total - pref_sum - num
            if pref_sum == suff_sum:
                return pivot
            pref_sum += num

        return -1

Type	Value
Time	O(n)
Space	O(1)

• Approach: Calculate total sum first. Then iterate through the array, maintaining a running prefix sum. At each index, the suffix sum is total - prefSum - arr[pivot]. If prefix equals suffix, return that index.
• Dry run (arr = [1,7,3,6,5,6]):
  • total = 28
  • pivot=0: prefSum=0, suffSum=28-0-1=27. Not equal. prefSum=1.
  • pivot=1: prefSum=1, suffSum=28-1-7=20. Not equal. prefSum=8.
  • pivot=2: prefSum=8, suffSum=28-8-3=17. Not equal. prefSum=11.
  • pivot=3: prefSum=11, suffSum=28-11-6=11. Equal! Return 3.

---

Neighbors Are Greater (Circular) (GeeksforGeeks)

Neighbors Are Greater (Circular)

Given a circular array A of N integers, for each element count how many of its two neighbors (left and right, wrapping around) are strictly greater than it. Print the count for each element.

Example:

Input: N = 5, A = [3, 6, 1, 4, 2]
Output: 1 0 2 0 2
Explanation:

• A[0]=3: left neighbor A[4]=2 (not greater), right neighbor A[1]=6 (greater) → 1
• A[1]=6: left neighbor A[0]=3 (not greater), right neighbor A[2]=1 (not greater) → 0
• A[2]=1: left neighbor A[1]=6 (greater), right neighbor A[3]=4 (greater) → 2
• A[3]=4: left neighbor A[2]=1 (not greater), right neighbor A[4]=2 (not greater) → 0
• A[4]=2: left neighbor A[3]=4 (greater), right neighbor A[0]=3 (greater) → 2

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();
        for (int i = 0; i < N; i++) {
            int count = 0;
            if (A[(i - 1 + N) % N] > A[i]) count++;
            if (A[(i + 1) % N] > A[i]) count++;
            System.out.print(count + " ");
        }
    }
}

class Main:
    def main(self):
        import sys
        input_data = sys.stdin.read().split()
        if not input_data: return
        N = int(input_data[0])
        A = [int(x) for x in input_data[1:N+1]]

        for i in range(N):
            count = 0
            if A[(i - 1 + N) % N] > A[i]:
                count += 1
            if A[(i + 1) % N] > A[i]:
                count += 1
            print(count, end=" ")
        print()

Type	Value
Time	O(n)
Space	O(1)

• Dry run (N=5, A=[3,6,1,4,2]):
  • i=0: left=A[4]=2>3? no; right=A[1]=6>3? yes → 1
  • i=1: left=3>6? no; right=1>6? no → 0
  • i=2: left=6>1? yes; right=4>1? yes → 2
  • i=3: left=1>4? no; right=2>4? no → 0
  • i=4: left=4>2? yes; right=3>2? yes → 2
  • Output: 1 0 2 0 2

---

Maximum Subarray (LeetCode 53)

53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int s = nums[0];
        for (int i = 1; i < nums.length; i++) {
            s = Math.max(nums[i], s + nums[i]);
            max = Math.max(max, s);
        }
        return max;
    }
}

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        curr_sum = nums[0]
        for i in range(1, len(nums)):
            curr_sum = max(nums[i], curr_sum + nums[i])
            max_sum = max(max_sum, curr_sum)
        return max_sum

Type	Value
Time	O(n)
Space	O(1)

• Approach: Kadane's Algorithm. Maintain current sum s and a global max. Start a new subarray if nums[i] is greater than s + nums[i].
• Dry run (nums = [-2,1,-3,4,-1,2,1,-5,4]):
  • i=0, max=-2, s=-2
  • i=1, num=1, s=max(1,-1)=1, max=1
  • i=2, num=-3, s=max(-3,-2)=-2, max=1
  • i=3, num=4, s=max(4,2)=4, max=4
  • Returns max=6 for subarray [4,-1,2,1].

---

Subarray Sum Equals K (LeetCode 560)

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.

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

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

import java.util.HashMap;
class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); 
        int sum = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum + nums[i]; 
            if (map.containsKey(sum - k)) {
                count = count + map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        pref_sum = 0
        d = {0: 1}
        for num in nums:
            pref_sum += num
            if pref_sum - k in d:
                count += d[pref_sum - k]
            d[pref_sum] = d.get(pref_sum, 0) + 1
        return count

Type	Value
Time	O(n)
Space	O(n)

• Approach: Maintain a running sum (prefix sum) and a HashMap that stores the frequency of prefix sums seen so far. If prefix_sum - k exists in the map, it means there are subarrays ending at the current index whose sum is k.
• Dry run (nums = [1,2,3], k = 3):
  • pref_sum=0, map={0:1}, count=0
  • num=1: pref_sum=1. pref_sum-k = -2 not in map. map={0:1, 1:1}
  • num=2: pref_sum=3. pref_sum-k = 0 in map. count += map[0] -> count=1. map={0:1, 1:1, 3:1}
  • num=3: pref_sum=6. pref_sum-k = 3 in map. count += map[3] -> count=2. map={0:1, 1:1, 3:1, 6:1}
  • Returns count=2.

---

Count Subarrays with Given Sum and Distinct Count (Custom)

Given an array of N integers, a target sum, and a number distinct, count how many subarrays have both the given sum and exactly distinct unique elements.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int target = sc.nextInt();
        int distinct = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int count = 0;

        for (int i = 0; i < n; i++) {
            int sum = 0;
            HashSet<Integer> set = new HashSet<>();

            for (int j = i; j < n; j++) {
                sum += arr[j];
                set.add(arr[j]);

                if (sum == target && set.size() == distinct) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

def count_subarrays(arr, target, distinct):
    n = len(arr)
    count = 0
    for i in range(n):
        s = 0
        seen = set()
        for j in range(i, n):
            s += arr[j]
            seen.add(arr[j])
            if s == target and len(seen) == distinct:
                count += 1
    return count

Type	Value
Time	O(n²)
Space	O(n)

• Approach: Brute force — enumerate all subarrays, maintaining a running sum and a set of distinct elements. Count those matching both conditions.

---

Product of Array Except Self (leetcode 238)

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        result[0] = 1;
        for(int i = 1; i < n; i++){
            result[i] = result[i - 1] * nums[i - 1];
        }
        int right = 1;
        for(int i = n - 1; i >= 0; i--){
            result[i] = result[i] * right;
            right = right * nums[i];
        }
        return result;
    }
}

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        for i in range(1, n):
            result[i] = result[i-1] * nums[i-1]
        right = 1
        for i in range(n-1, -1, -1):
            result[i] *= right
            right *= nums[i]
        return result

Feature	Value
Time	O(n)
Space	O(1) extra
Works with zero	Yes

• Approach: Calculate prefix products and suffix products separately, then multiply them.
• Dry run (nums = [1,2,3,4]):
  • Left products: [1, 1, 2, 6]
  • Right products: [24, 12, 4, 1]
  • Result: [24, 12, 8, 6]

---

Maximum Product Subarray (LeetCode 152)

152. Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

class Solution {
    public int maxProduct(int[] nums) {
        int pl = 1, pr = 1, r = Integer.MIN_VALUE;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (pl == 0) pl = 1;
            if (pr == 0) pr = 1;
            pl *= nums[i];
            pr *= nums[n - 1 - i];
            r = Math.max(r, Math.max(pl, pr));
        }
        return r;
    }
}

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        pl=1
        pr=1
        r=float("-inf")
        for i in range(len(nums)):
            if pl==0 :
                pl=1
            pl*=nums[i]
            if pr==0:
                pr=1
            pr*=nums[len(nums)-i-1]
            r=max(r,pl,pr)
        return r

Type	Value
Time	O(n)
Space	O(1)

• Approach: Prefix product and suffix product. Compare to max, reset product to 1 if we hit a zero.
• Dry run (nums=[2,3,-2,4]):
  • pl=[2,6,-12,-48], pr=[4,-8,-24,-48]. Max is 6. Returns 6.

---

Maximum Product Subset of an Array (GeeksforGeeks)

Maximum Product Subset of an Array

Given an array nums with N integers. Find the maximum product possible by multiplying any subset of the array.

Example 1:

Input: nums = [-1, -1, -2, 4, 3]
Output: 24
Explanation: Maximum product will be ( -1 _ -2 _ 4 * 3 ) = 24

class Solution {
    int maxProductSubset(int nums[], int n) {
        int prod = 1;
        int negCount = 0;
        int zeroCount = 0;
        int maxNeg = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num == 0) {
                zeroCount++;
                continue;
            }
            if (num < 0) {
                negCount++;
                maxNeg = Math.max(maxNeg, num);
            }
            prod *= num;
        }
        if (zeroCount == nums.length) return 0;
        if (negCount % 2 != 0) {
            if (negCount == 1 && zeroCount > 0) return 0;
            prod /= maxNeg;
        }
        return prod;
    }
}

class Solution:
    def maxProductSubset(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]
        prod = 1
        neg_count = 0
        zero_count = 0
        max_neg = float('-inf')
        for num in nums:
            if num == 0:
                zero_count += 1
                continue
            if num < 0:
                neg_count += 1
                max_neg = max(max_neg, num)
            prod *= num
        if zero_count == len(nums): return 0
        if neg_count % 2 != 0:
            if neg_count == 1 and zero_count > 0:
                return 0
            prod //= max_neg
        return prod

Type	Value
Time	O(n)
Space	O(1)

• Approach: Loop through to count zeros and negatives and keep tracking the max negative. Multiply all non-zero elements. If odd number of negatives, divide product by max negative.
• Dry run (nums=[-1, -1, -2, 4, 3]):
  • Max neg is -1. Product of all non-zeros is -24. Odd negatives (3). Divide by max neg (-1) to get 24.

---

Best Time to Buy and Sell Stock (leetcode 121)

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: No transaction yields a positive profit, so max profit = 0.

class Solution {
    public int maxProfit(int[] prices) {
        int p=prices[0],sell=0;
        for(int i:prices){
            if(i<p) p=i;
            else if (i-p>sell) sell=i-p;
        }
     return sell;
}}

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        p = prices[0]
        sell = 0
        for price in prices:
            if price < p:
                p = price
            elif price - p > sell:
                sell = price - p
        return sell

Type	Value
Time	O(n)
Space	O(1)

• Approach: Track min price and max profit.
• Dry run (prices = [7,1,5,3,6,4]):
  • p=7, sell=0
  • i=1: p=1, sell=0
  • i=2: p=1, sell=4
  • i=3: p=1, sell=4
  • i=4: p=1, sell=5
  • i=5: p=1, sell=5 → Answer is 5.

---

Best Time to Buy and Sell Stock II (LeetCode 122)

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

Type	Value
Time	O(n)
Space	O(1)

• Approach: Add all local maximum profits when price increases.
• Dry run (prices=[7,1,5,3,6,4]):
  • i=2: 5 > 1 -> profit+=4
  • i=4: 6 > 3 -> profit+=3
  • Returns 7.

---

Jump Game (leetcode 55)

55. Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

class Solution {
    public boolean canJump(int[] nums) {
        int m=0;
        for(int i=0;i<nums.length;i++){
            if(i>m) return false;
            m=Math.max(m,i+nums[i]);
        }
        return true;

    }
}

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        m = 0
        for i, val in enumerate(nums):
            if i > m:
                return False
            m = max(m, i + val)
        return True

Type	Value
Time	O(n)
Space	O(1)

• Approach: Keep track of the maximum reachable index (m). If current index i is greater than m, it's unreachable. Otherwise, update m.
• Dry run (nums = [2,3,1,1,4]):
  • i=0, val=2 → m=max(0, 0+2)=2
  • i=1, val=3 → m=max(2, 1+3)=4
  • Return true since we can reach the end.

---

Gas Station (LeetCode 134)

134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station.
Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

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

Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        int n = gas.length;
        for(int i = 0; i < n; i++){
            totalGas += gas[i];
            totalCost += cost[i];
        }
        if(totalGas < totalCost) return -1;
        
        int currGas = 0, startInd = 0;
        for(int i = 0; i < n; i++){
            currGas += gas[i] - cost[i];
            if(currGas < 0){
                startInd = i + 1;
                currGas = 0;
            }
        }
        return startInd;
    }
}

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
            
        curr_gas = 0
        start_idx = 0
        for i in range(len(gas)):
            curr_gas += gas[i] - cost[i]
            if curr_gas < 0:
                start_idx = i + 1
                curr_gas = 0
                
        return start_idx

Type	Value
Time	O(n)
Space	O(1)

• Approach: First, check if total gas generated is at least total gas consumed. If not, impossibility is guaranteed. If enough gas exists overall, we can maintain the running tally of gas. Every time the running tally goes below 0, it means we can't start at any station up to this point. So we set the next station as the potential starting index and reset the tally.
• Dry run (gas=[1,2,3,4,5], cost=[3,4,5,1,2]):
  • Total Gas 15 >= Total Cost 15 -> valid solution exists.
  • index 0: 1 - 3 = -2 < 0 -> start=1, curr=0.
  • index 1: 2 - 4 = -2 < 0 -> start=2, curr=0.
  • index 2: 3 - 5 = -2 < 0 -> start=3, curr=0.
  • index 3: 4 - 1 = 3 -> curr=3.
  • index 4: curr=3 + 5 - 2 = 6 -> curr=6.
  • Returns start index 3.

---

Hackerland Radio Transmitters (HackerRank)

Hackerland Radio Transmitters

A city has N houses located at different positions on a straight line.
You need to install radio transmitters so that every house is covered.

• A transmitter can be installed only at the location of a house.
• A transmitter covers all houses within R units to its left and right.
• Find the minimum number of transmitters required to cover all houses.

Example:
Input: N = 5, A = [1, 2, 3, 5, 9], R = 1
Output: 3
Explanation: Place transmitters at houses at index 1 (value 2), index 3 (value 5), and index 4 (value 9).

import java.util.*;
public class Solution {
    public static int hackerlandRadioTransmitters(int[] x, int k) {
        Arrays.sort(x);
        int n = x.length;
        int i = 0;
        int count = 0;
        while (i < n) {
            // Leftmost uncovered house
            int start = x[i];
            // Move to the farthest house within range k
            while (i < n && x[i] <= start + k) {
                i++;
            }
            // Place transmitter at the previous house
            int transmitter = x[i - 1];
            // Skip all houses covered by this transmitter
            while (i < n && x[i] <= transmitter + k) {
                i++;
            }
            count++;
        }
        return count;
    }
}

class Solution:
    def hackerlandRadioTransmitters(self, x: List[int], k: int) -> int:
        x.sort()
        n = len(x)
        i = 0
        count = 0
        while i < n:
            start = x[i]
            while i < n and x[i] <= start + k:
                i += 1
            transmitter = x[i - 1]
            while i < n and x[i] <= transmitter + k:
                i += 1
            count += 1
        return count

Type	Value
Time	O(n log n)
Space	O(1)

• Approach: Greedy algorithm. First sort the array. Starting from the leftmost house, find the farthest house within range k that can cover it. Place a transmitter there, then find the farthest house covered by this transmitter to the right, and start search for the next transmitter after that house.
• Dry run (x = [1, 2, 3, 5, 9], k = 1):
  • i=0: start = 1. Farthest within 1+1=2 is house 2. transmitter at 2. Skip houses <= 2+1=3 (house 3). i becomes 3. count=1.
  • i=3: start = 5. Farthest within 5+1=6 is house 5. transmitter at 5. Skip houses <= 5+1=6 (house 5). i becomes 4. count=2.
  • i=4: start = 9. Farthest within 9+1=10 is house 9. transmitter at 9. Skip houses <= 9+1=10 (house 9). i becomes 5. count=3.
  • Return 3.

---

Check if Array Is Sorted and Rotated (LeetCode 1752)

1752. Check if Array Is Sorted and Rotated

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.
There may be duplicates in the original array.

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

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

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

class Solution {
    public boolean check(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
        }
        return count <= 1;
    }
}

class Solution:
    def check(self, nums: List[int]) -> bool:
        count = 0
        n = len(nums)
        for i in range(n):
            if nums[i] > nums[(i + 1) % n]:
                count += 1
        return count <= 1

Type	Value
Time	O(n)
Space	O(1)

• Approach: A sorted and rotated array can have at most one "drop" (a point where current element is greater than the next). We count the drops (including from the last element to the first). If we have 0 or 1 drop, it is valid.
• Dry run (nums=[3,4,5,1,2]):
  • 3 > 4 false
  • 4 > 5 false
  • 5 > 1 true (count=1)
  • 1 > 2 false
  • 2 > 3 false (last element compared with first)
  • count <= 1, returns true.

---

Majority Element (LeetCode 169)

169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

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

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

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0, candidate = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = candidate = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

Type	Value
Time	O(n)
Space	O(1)

• Approach: Boyer-Moore Voting.
• Dry run (nums=[3,2,3]):
  • count=0 → candidate=3, count=1
  • num=2 → count=0
  • count=0 → candidate=3, count=1 → answer=3

---

Longest Consecutive Sequence (leetcode 128)

128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

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

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int longest = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) {
                int curr = n, temp = 1;

                while (set.contains(curr + 1)) {
                    curr++;
                    temp++;
                }

                longest = Math.max(longest, temp);
            }
        }
        return longest;
    }
}

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0
        for n in num_set:
            if (n - 1) not in num_set:
                curr = n
                temp = 1
                while (curr + 1) in num_set:
                    curr += 1
                    temp += 1
                longest = max(longest, temp)
        return longest

Type	Value
Time	O(n)
Space	O(n)

• Approach: Use a HashSet. Only start counting sequence lengths from sequence starting numbers (where n - 1 doesn't exist in the set).
• Dry run (nums = [100,4,200,1,3,2]):
  • 100: 99 not in set, checks only 100, length 1.
  • 4: 3 is in set, skip.
  • 200: 199 not in set, checks only 200, length 1.
  • 1: 0 not in set, counts 1,2,3,4, length 4.
  • Return max length 4.

---

Top K Frequent Elements (LeetCode 347)

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

Example 3:

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

import java.util.*;
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>(
            (a, b) -> countMap.get(a) - countMap.get(b)
        );

        for (int num : countMap.keySet()) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = heap.poll();
        }
        return result;
    }
}

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        heap = []
        m = {}
        for i in nums:
            m[i] = m.get(i, 0) + 1
        for key, value in m.items():
            heapq.heappush(heap, (value, key))
            if len(heap) > k:
                heapq.heappop(heap)
        ans = []
        while heap:
            ans.append(heapq.heappop(heap)[1])
        return ans

Type	Value
Time	O(n log k)
Space	O(n + k)

• Approach: Build a frequency map of elements. Use a min-heap (PriorityQueue in Java) of size k to keep track of the top k elements. Populate the heap based on frequencies. If heap size exceeds k, remove the least frequent element.
• Dry run (nums = [1,1,1,2,2,3], k = 2):
  • countMap = {1: 3, 2: 2, 3: 1}
  • Insert 1: heap = [1]
  • Insert 2: heap = [2, 1] (ordered by frequency: 2:2, 1:3)
  • Insert 3: heap = [3, 2, 1] (ordered by frequency: 3:1, 2:2, 1:3). heap.size() = 3 > 2 -> poll 3. heap = [2, 1]
  • result = [2, 1] -> return [1, 2] (or [2, 1], order doesn't matter).

---

Kth Largest Element in an Array (LeetCode 215)

215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> h=new PriorityQueue<>();
        for(int i=0;i<nums.length;i++){
            if(h.size()<k || nums[i]>h.peek()){
                h.add(nums[i]);
            }
            if(h.size()>k){
                h.poll();
            }
        }
        return h.peek();
    }
}

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        h = []
        for num in nums:
            if len(h) < k or num > h[0]:
                heapq.heappush(h, num)
            if len(h) > k:
                heapq.heappop(h)
        return h[0]

Type	Value
Time	O(n log k)
Space	O(k)

• Approach: Use a Min-Heap of size k. We maintain the k largest elements in the heap, and the root is the $k^{th}$ largest element overall.
• Dry run (nums = [3,2,1,5,6,4], k = 2):
  • i=0, num=3: heap=[3]
  • i=1, num=2: heap=[2, 3]
  • i=2, num=1: heap=[1, 2, 3] → size > 2, poll → heap=[2, 3]
  • i=3, num=5: heap=[2, 3, 5] → size > 2, poll → heap=[3, 5]
  • i=4, num=6: heap=[3, 5, 6] → size > 2, poll → heap=[5, 6]
  • i=5, num=4: 4 < heap.peek()=5, skip
  • Return heap.peek() = 5

---

Merge Intervals (LeetCode 56)

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

class Solution:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        m=[]
        intervals.sort()
        for interval in intervals:
            if not m or m[-1][1]<interval[0]:
                m.append(interval)
            else :
                m[-1][1]=max(interval[1],m[-1][1])
        return m
 

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

Type	Value
Time	O(n log n)
Space	O(n)

• Approach: Sort intervals by start time. Iteratively merge if end of last overlaps with current start.
• Dry run (intervals=[[1,3],[2,6]]):
  • [1,3] overlaps with [2,6] -> max(3,6)=6 -> [1,6].

---

Check if Strings Can be Made Equal With Operations II (LeetCode 2840)

2840. Check if Strings Can be Made Equal With Operations II

You are given two strings s1 and s2, both of length n, consisting of lowercase English letters.

You can apply the following operation on any of the two strings any number of times:

• Choose any two indices i and j such that i < j and the difference j - i is even, then swap the two characters at those indices in the string.

Return true if you can make the strings s1 and s2 equal, and false otherwise.

Example 1:

Input: s1 = "abcdba", s2 = "cabdab"
Output: true

Example 2:

Input: s1 = "abe", s2 = "bea"
Output: false

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        od = [0] * 26
        ed = [0] * 26
        for i in range( len(s1)):
            if i % 2 == 1:
                od[ord(s1[i]) - ord("a")] +=1
                od[ord(s2[i]) - ord("a")] -= 1
            else:
                ed[ord(s1[i]) - ord("a")] += 1
                ed[ord(s2[i]) - ord("a")] -= 1
        return od == [0] * 26 and ed == [0] * 26

class Solution {
    public boolean checkStrings(String s1, String s2) {
        int[] odd = new int[26];
        int[] even = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            if (i % 2 == 1) {
                odd[s1.charAt(i) - 'a']++;
                odd[s2.charAt(i) - 'a']--;
            } else {
                even[s1.charAt(i) - 'a']++;
                even[s2.charAt(i) - 'a']--;
            }
        }
        for (int i = 0; i < 26; i++) {
            if (odd[i] != 0 || even[i] != 0) return false;
        }
        return true;
    }
}

Type	Value
Time	O(n)
Space	O(1)

• Approach: Character counts at even and odd indices must match between both strings.
• Dry run (s1="abe", s2="bea"):
  • even={a:1,e:1}, {b:1,a:1} -> mismatch -> returns false.

---