Diagonal Traversal

 eg. 

1     2     3     4

5     6     7     8

9    10   11   12

13  14   15   16

Output: 1 6 11 16 2 7 12 3 8 4 

Approach:
number of diagonals = arr.length
all the diagonals are starting from i=0,
till j=arr.length that will act as right wall

package jan24_2D_Array;

public class DiagonalTraversal {
    public static void main(String[] args) {

        int[][] arr = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        };

        /*
         Time Complexity:
         Best Case: O(n^2) – All diagonals are visited once.
         Average Case: O(n^2) – Diagonal traversal over matrix elements.
         Worst Case: O(n^2) – Covers upper half of matrix diagonals.

         Space Complexity:
         Best/Average/Worst Case: O(1) – No extra space used, in-place processing.
        */

        
        for (int diagonal = 0; diagonal < arr.length; diagonal++) {
            for (int i = 0, j = diagonal; j < arr.length; i++, j++) {
                System.out.print(arr[i][j] + "\t");
            }
        }
    }
}

Case
Time Complexity
Explanation
Space Complexity
Explanation
Best
O(n²)
All diagonals are visited once
O(1)
No extra space used
Average
O(n²)
Diagonal traversal over matrix
O(1)
In-place processing
Worst
O(n²)
Covers upper half of matrix
O(1)
No additional memory used

Exit Point

Given a binary matrix of size N x M, you enter the matrix at cell (0, 0) in the left to the right direction. Whenever encountering a 0  retain in the same direction if encountered a 1 change direction to the right of the current direction and change that 1 value to 0,  find out exit point from the Matrix.

Examples: 

Input: matrix = {{0, 1, 0},

                          {0, 1, 1},

                          {0, 0, 0}}
Output: 1 0
Explanation: 
Enter the matrix at 0, 0 -> then move towards 0, 1 ->  1 is encountered -> turn right towards 1, 1 -> again 1 is encountered -> turn right again towards 1, 0 -> now, the boundary of matrix will be crossed ->hence, exit point reached at 1, 0.

package jan22_2D_Array;

public class ExitPoint {
    public static void main(String[] args) {

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

        /*
        East = 0 i.e. (i, j+1)
        South = 1 i.e. (i+1, j)
        West = 2 i.e. (i, j-1)
        North = 3 i.e. (i-1, j)
        */

        int direction = 0;
        int i = 0, j = 0;

        /*
         * Time Complexity: O(m * n) in the worst case (when all cells are visited)
         * Space Complexity: O(1), constant extra space used
         */

        while (true) {

            direction = (direction + arr[i][j]) % 4;

            // Move in the current direction
            if (direction == 0)
                j++;       // East
            else if (direction == 1)
                i++;       // South
            else if (direction == 2)
                j--;       // West
            else if (direction == 3)
                i--;       // North

            // Exit if out of bounds and step back once
            if (i < 0) {
                i++;
                break;
            } else if (j < 0) {
                j++;
                break;
            } else if (i == arr.length) {
                i--;
                break;
            } else if (j == arr[0].length) {
                j--;
                break;
            }
        }

        System.out.println(i + "," + j);
    }
}

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(m × n)	O(1)
Worst	O(m × n)	O(1)

Explanation:

• Best Case: Exits the matrix immediately (e.g., first cell directs out).

• Average/Worst Case: Traverses many or all cells before exiting.

• Space Complexity is always O(1) as only a few variables (i, j, direction) are used regardless of input size.

LeetCode 154. Find Minimum in Rotated Sorted Array II

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5]

Output: 1

Example 2:

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

Output: 0

 

Constraints:

n == nums.length

1 <= n <= 5000

-5000 <= nums[i] <= 5000

nums is sorted and rotated between 1 and n times.

package LeetCode.binarySearch;

public class LT154_SearchInRotatedSortedArray_duplicates {

    public static void main(String[] args) {
        int[] arr = {1};

        System.out.println(findMin(arr));
        // TC: O(log n) in best/average case, O(n) in worst case due to duplicates
        // SC: O(1)
    }

    public static int findMin(int[] nums) {
        int low = 0, high = nums.length - 1; // SC: O(1), initializing variables

        int min = Integer.MAX_VALUE; // SC: O(1), auxiliary variable to track min
        while (low <= high) {        // TC: O(log n) best/avg, O(n) worst when duplicates reduce one by one
            int mid = low + (high - low) / 2; // SC: O(1)

            if (nums[low] < nums[high]) {    // TC: O(1), check if already sorted
                return Integer.min(nums[low], min); // SC: O(1)
            }

            if (nums[low] == nums[mid] && nums[mid] == nums[high]) { // TC: O(1)
                min = Integer.min(nums[low], min); // SC: O(1)
                low++;  // TC: O(1)
                high--; // TC: O(1)
            }
            // left half is sorted
            else if (nums[low] <= nums[mid]) {  // TC: O(1)
                min = Integer.min(nums[low], min); // SC: O(1)
                low = mid + 1; // TC: O(1)
            } else {
                min = Integer.min(nums[mid], min); // SC: O(1)
                high = mid - 1; // TC: O(1)
            }
        }

        return min; // SC: O(1)
    }
}

Here’s the Time and Space Complexity of the findMin function in a clear table format:

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(log n)	O(1)
Worst	O(n)	O(1)

Explanation:

• Best Case: The array is already sorted (nums[low] < nums[high]).

• Average Case: Standard binary search logic with occasional duplicates.

• Worst Case: All or many elements are duplicates, causing the loop to degrade into linear time.

LeetCode 153. Find Minimum in Rotated Sorted Array I

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

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

 Example 1:

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

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]

Output: 0

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]

Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

{4, 5, 6, 7, 0, 1, 2, 3}

{7, 8, 0, 1, 2, 3, 4, 5, 6}

{4, 5, 1, 2, 3}

package LeetCode.binarySearch;

public class LT153_SearchInRotatedSortedArray3 {

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

        System.out.println(search(arr));

    }

    public static int search(int[] nums) {
        int low = 0;                       // O(1) time & space
        int high = nums.length - 1;        // O(1) time & space
        int min = Integer.MAX_VALUE;       // O(1) time & space

        // Loop will run at most O(log n) times since we halve the search space each iteration
        while (low <= high) {              // O(log n) time
            int mid = low + (high - low) / 2;  // O(1) time & space

            // if search space is already sorted
            // then always arr[low] will be smaller
            if (nums[low] <= nums[high]) {
                min = Math.min(min, nums[low]);
                break;
            }

            // Left half is sorted
            if (nums[low] <= nums[mid]) { // O(1) time
                // get minimum
                min = Math.min(min, nums[low]); // O(1) time

                // eliminate left half
                low = mid + 1;            // O(1) time & space
            }
            // Right half is sorted
            else {
                // get minimum
                min = Math.min(min, nums[mid]); // O(1) time

                // eliminate right half
                high = mid - 1;           // O(1) time & space
            }
        }

        return min;                       // O(1) time & space
    }
}

Time Complexity (TC):

Best Case: O(1) — minimum found immediately

Average Case: O(log n) — binary search halving the array

Worst Case: O(log n) — rotated array causes full binary search traversal
Space Complexity (SC):

Best/Average/Worst Case: O(1) — only constant extra space used

LeetCode 81. Search in Rotated Sorted Array II

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/ 

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

 Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3

Output: false

Example 3: EDGE CASE

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

Output: true

package LeetCode.binarySearch;

public class LT81_SearchInRotatedSortedArray2 {

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

        int target = 0;

        boolean idx = search(arr, target);
        System.out.println(idx);

    }

    /**
     * Time Complexity:
     * - Best / Average Case: O(log n), due to binary search.
     * - Worst Case: O(n), when duplicates force linear scan (e.g., [1,1,1,1,1,1,2,1]).
     * Space Complexity: O(1), constant space used.
     */
    public static boolean search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            // Check mid
            if (nums[mid] == target)
                return true;

            // Handle duplicates on both ends
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low++;
                high--;
            }
            // Left half is sorted
            else if (nums[low] <= nums[mid]) {
                if (nums[low] <= target && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            // Right half is sorted
            else {
                if (nums[mid] < target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }

        return false;
    }

}

Case	Time Complexity	Space Complexity	Explanation
Best	O(1)	O(1)	Target found at the middle index in the first comparison.
Average	O(log n)	O(1)	Normal binary search behavior when duplicates are minimal or non-impactful.
Worst	O(n)	O(1)	When duplicates prevent binary decision, forcing linear reduction (e.g., [1,1,1,1,2,1]).

Example: WORST CASE EG.

int[] nums = {2, 2, 2, 2, 3, 2, 2};

int target = 3;

👇 What happens during binary search:

1. Initial State:

   low = 0, high = 6, mid = 3
   nums[mid] = 2, nums[low] = 2, nums[high] = 2
   

   • Since nums[low] == nums[mid] == nums[high], we can't tell which side is sorted.

   • So we do:

     low++, high--;

   • This continues, narrowing the range one step at a time, just like linear search.

2. This repeats until we find 3 or exhaust the array.

⚠️ Why This Is Bad:

• Because we can't divide the array in half using binary logic due to all elements being the same.

• So we reduce low and high by 1 each time — leading to O(n) time.

LeetCode 33. Search in Rotated Sorted Array I

 https://leetcode.com/problems/search-in-rotated-sorted-array/

https://www.youtube.com/watch?v=5qGrJbHhqFs&list=PLgUwDviBIf0pMFMWuuvDNMAkoQFi-h0ZF&index=5 

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

Example 3:

Input: nums = [1], target = 0

Output: -1

 

Constraints:

• 1 <= nums.length <= 5000

• -104 <= nums[i] <= 104

• All values of nums are unique.

• nums is an ascending array that is possibly rotated.

• -104 <= target <= 104

package LeetCode.binarySearch;

public class LT33_SearchInRotatedSortedArray {

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

        int target = 0;

        int idx = search(arr, target);
        System.out.println(idx);

    }

    public static int search(int[] nums, int target) {
        // Time Complexity: O(log n)
        // Space Complexity: O(1)

        int low = 0, high = nums.length - 1;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (nums[mid] == target)
                return mid;

                // LEFT HALF IS SORTED
            else if (nums[low] <= nums[mid]) {

                if (nums[low] <= target && target <= nums[mid])
                    // Target lies in the left half
                    high = mid - 1;
                else
                    // Target lies in the right half
                    low = mid + 1;
            } else {
                // RIGHT HALF IS SORTED
                if (nums[mid] <= target && target <= nums[high])
                    // Target lies in the right half
                    low = mid + 1;
                else
                    // Target lies in the left half
                    high = mid - 1;
            }
        }

        return -1; // Target not found
    }
}


    }

🔍 Summary

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(log n)	O(1)
Worst	O(log n)	O(1)

Any base multiplication

1. You are given a base b

2. You are given 2 numbers n1 and n2 of base b

3. You are required to multiply n1 and n2 and print the value

Input Format:

- A base b

- A number n1

- A number n2

Output:

diff of n2 & n1 in base b

Constraints:

2 <= b <= 10

0 <= n1 <= 10000

0 <= n2 <= 10000

Input: 

5

1220

31

package jan19;

public class AnyBaseMultiplication {

    public static void main(String[] args) {
        int n1b8 = 2156;
        int n2b8 = 74;
        int base = 8;

        int product = getProduct(n1b8, n2b8, base);  // O(d2 * d1) where d2 = digits of n2, d1 = digits of n1
        System.out.println(product);
    }

    /**
     * Time Complexity: O(d2 × d1), where d1 = number of digits in n1b8 and d2 = number of digits in n2b8
     * Space Complexity: O(1) – constant extra space used (no dynamic data structures)
     */
    private static int getProduct(int n1b8, int n2b8, int base) {
        int finalAns = 0, power = 0;

        while (n2b8 > 0) { // O(d2)
            int n = n2b8 % 10;
            n2b8 = n2b8 / 10;

            // single digit multiplication + positional shift
            int singleProduct = anyBaseMultiplicationSingleDigit(n1b8, n, base) * (int) Math.pow(10, power++);

            // sum of partial product with the result so far
            finalAns = getSum(finalAns, singleProduct, base); // O(d1)
        }

        return finalAns;
    }

    /**
     * Multiplies a number with a single digit in any base
     * Time Complexity: O(d1) – d1 = number of digits in n1b8
     * Space Complexity: O(1)
     */
    private static int anyBaseMultiplicationSingleDigit(int n1b8, int n, int base) {

        int carry = 0, ans = 0, power = 0, remainder = 0;

        while (n1b8 > 0) { // O(d1)
            int a = n1b8 % 10;
            n1b8 = n1b8 / 10;

            int product = a * n + carry;

            carry = (product >= base) ? product / base : 0;
            remainder = product % base;

            ans += remainder * (int) Math.pow(10, power++);
        }

        // Add leftover carry
        ans = carry != 0 ? ans + (carry * (int) Math.pow(10, power++)) : ans;

        return ans;
    }

    /**
     * Adds two numbers in a given base
     * Time Complexity: O(max(d1, d2)) – number of digits in max(n1B8, n2B8)
     * Space Complexity: O(1)
     */
    private static int getSum(int n1B8, int n2B8, int base) {
        int carry = 0, ans = 0, power = 0;

        while (n1B8 > 0 || n2B8 > 0 || carry > 0) { // O(max(d1, d2))
            int a = n1B8 % 10;
            int b = n2B8 % 10;
            n1B8 = n1B8 / 10;
            n2B8 = n2B8 / 10;

            int sum = a + b + carry;
            carry = sum / base;

            ans += (sum % base) * (int) Math.pow(10, power++);
        }

        return ans;
    }
}

📊 Time and Space Complexity Summary Table:

Operation
Time Complexity
Space Complexity
getProduct(n1, n2, base)
O(d1 × d2)
O(1)
anyBaseMultiplicationSingleDigit
O(d1)
O(1)
getSum
O(max(d1, d2))
O(1)
d1 = number of digits in n1b8
d2 = number of digits in n2b8
📊 Complexity Table
Case
Time Complexity
Space Complexity
Explanation
Best
O(d1 × d2)
O(1)
Even in the best case (e.g., multiplying by 0 or 1), we still iterate over digits of both numbers due to multiplication and addition logic.
Average
O(d1 × d2)
O(1)
Typical input: both numbers have several digits and require full traversal.
Worst
O(d1 × d2)
O(1)
Maximum digits in both inputs. Also includes carry propagation across all digits in each addition.
 
🔍 Why O(d1 × d2)?
For each digit of n2 (let’s say it has d2 digits), we:
Multiply entire n1 (d1 digits) → O(d1)
Add result to final answer → O(d1) (since result grows gradually)
So total time: d2 × O(d1) → O(d1 × d2)

🧠 Why O(1) Space?
Only a few integer variables are used (carry, power, ans).
No recursion or dynamic data structure