Leet Code 442. Find All Duplicates in an Array

 https://leetcode.com/problems/find-all-duplicates-in-an-array/

Example 1:

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

package pep.Day62;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

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

        int[] arr = new int[]{4, 3, 2, 7, 8, 2, 3, 1};
        System.out.print(findDuplicates1(arr));

    }

    public static List<Integer> findDuplicates(int[] nums) {
        int i = 0, n = nums.length;
        List<Integer> ans = new LinkedList<>();

        while (i < n) {

            if (nums[nums[i] - 1] == nums[i]) {
                i++;
            } else {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }

        }

        i = 0;
        while (i < n) {
            if (nums[i] - 1 != i)
                ans.add(nums[i]);
            i++;
        }

        return ans;
    }

    // using on one for loop
    // logic: jo bhi number first time mil gya usko -ve kr do, 
    // and jab woh second time milega to ans me add
    public static Set<Integer> findDuplicates1(int[] nums) {
        int i = 0, n = nums.length;
        Set<Integer> ans = new HashSet<>();

        while (i < n) {
            // agr number pehle se hi -ve hai, means visit ho chuka hai yeh
            if (nums[i] <0)
                i++;
            // -ve of mera number and usko sahi position pr jo number hai dono same hai
            // hence, add in ans
            else if (nums[nums[i] - 1] == -1 * nums[i]) {
                ans.add(nums[i]);
                i++;
            } else {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = -1 * nums[i];
                nums[i] = temp;
            }

        }

//        i = 0;
//        while (i < n) {
//            if (nums[i] - 1 != i)
//                ans.add(nums[i]);
//            i++;
//        }

        return ans;
    }
}

Leet Code 838. Push Dominoes

https://leetcode.com/problems/push-dominoes/

Example 1:

Input: dominoes = "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

package pep.Day62;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_838_Push_dominoes {
    public static void main(String[] args) {
        System.out.print(pushDominoes(".L.R...LR..L.."));
    }

    public static String pushDominoes(String dominoes) {
        Queue<Pair> que = new LinkedList<>();
        char[] str = dominoes.toCharArray();

        // yha pr humne pairs bnakr queue me add kr diya
        for (int i = 0; i < str.length; i++) {
            char c = str[i];
            if (c != '.')
                que.add(new Pair(c, i));
        }

        while (!que.isEmpty()) {
            Pair remove = que.remove();
            if (remove.status == 'L') {
                // condition: index min. 1 hona cheye, tabhi 0th index ka check ho paega
                if (remove.index > 0 && str[remove.index - 1] == '.') {
                    str[remove.index - 1] = 'L';
                    que.add(new Pair('L', remove.index - 1));
                }
            } else {
                // condition: agr jo remove kiya hai uska index +1 chota hona chye mere array se
                // aur uski right me next position pr dot hona cheye
                // toh yeh mera potential right bnn skta hai
                if (remove.index + 1 < str.length && str[remove.index + 1] == '.') {
                    // agr right ki next of next me Left wala exist krta hai
                    // to left wale ko bhi remove kr denge
                    if (remove.index + 2 < str.length && str[remove.index + 2] == 'L') {
                        que.remove();
                    } else {
                        str[remove.index+1] = 'R';
                        que.add(new Pair('R', remove.index + 1));
                    }
                }

            }
        }

        return new String(str);

    }

    static class Pair {
        char status;
        int index;

        Pair(char status, int index) {
            this.status = status;
            this.index = index;
        }
    }
}

Leet Code 41. First Missing Positive

https://leetcode.com/problems/first-missing-positive/ 

Example 1:

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

jo bhi number inrange hai na, jese 5th index pr 2 mila toh 2 ko 2nd index wale number ke sath swap kr do, toh jo number present hain woh aopni sahi jgh pr pauch jaenge 

then, array ko traverse krnege toh, 0th index pr 1 hona chye, jh apr bhi aesa na ho, whi index wala number hi humara answer bnn jaega.

public class LeetCode_41_First_Missing_Positive {
    // brute force: pehle sort kr do, then, check kro pehle no. 1 hona cheye then 2...
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, -1, 1};
        System.out.print(firstMissingPositive(arr));
    }

    public static int firstMissingPositive(int[] nums) {
        int i = 0, n = nums.length;

        while (i < n) {
            if (nums[i] > 0 && nums[i] < n + 1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            } else {
                i++;
            }
        }

        i = 0;
        while (i < n) {
            if (nums[i] != i++ + 1)
                return i;
        }

        return n + 1;
    }

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

Leet Code 152. Maximum Product Subarray

https://leetcode.com/problems/maximum-product-subarray/

Example 1:

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

                                                

 

package pep.Day62;

public class LeetCode_152_Maximum_Product_Subarray {
    public static void main(String[] args) {
        int[] arr = new int[]{-2, 1, 0, 3, 4, -1, 6, -2};
        System.out.print(maxProduct(arr));
    }

    public static int maxProduct(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int product = 1;

        // pehle left boundary se start krenge
        for (int i = 0; i < nums.length; i++) {
            product *= nums[i];
            ans = Math.max(ans, product);
            if (product == 0) {
                product = 1;
            }
        }

        // right boundary se start krenge
        product = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            product *= nums[i];
            ans = Math.max(ans, product);
            if (product == 0) {
                product = 1;
            }
        }

        return ans;
    }
}