Such a Dummy Programmer

26. Remove Duplicates from Sorted Array

Easy

9.5K

13.1K

Apple

Amazon

Adobe

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.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

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).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Beats 100% solutions

View my solution here

class Solution {

    public int removeDuplicates(int[] nums) {
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0;i<nums.length ; i++)
        {

            if(i == nums.length-1)
            {
                arr.add(nums[i]);
            }
            else if(nums[i] == nums[i+1] )
            {

            }
            else
            {
                arr.add(nums[i]);
            }
        }

        for(int i=0;i<nums.length ; i++)
        {
            if( i > arr.size()-1)
            {
                
            }
            else
            {
                nums[i] = arr.get(i);
            }
            
        }
        return arr.size();

    }
}

14. Longest Common Prefix

Easy

11.5K

3.6K

Amazon

Apple

Google

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

View explanation of the solution here -

https://leetcode.com/problems/longest-common-prefix/solutions/2863919/java-easy-beats-99-of-solution-in-terms-of-memory-and-runtime/

and here -

class Solution {

    public String longestCommonPrefix(String[] strs) {

        Arrays.sort(strs);

        if(strs.length ==0 || strs[0].length()==0)

{

            return "";

}

        int c=0;

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

{

            if(strs[0].charAt(i)==strs[strs.length-1].charAt(i))

{

                c=c+1;

}

            else

{

                break;

}

}

        return c ==0 ? "" : strs[0].substring(0,c);

}

}

20. Valid Parentheses
Easy
17K
879
Amazon
BlackRock
Bloomberg
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
 
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
 
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

See my solution explained here

Solution -

class Solution {

    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();

        for(Character c:s.toCharArray())

{

            if(c == '{')

{

                stack.push('{');

}

            else if (c == '(')

{

                stack.push('(');

}

            else if (c == '[')

{

                stack.push('[');

}

            else

{

                if(!stack.isEmpty())

{

                Character top = stack.peek();

                Character sig1 = ')';

                if(top == '(' && c == ')')

                    stack.pop();

                else if (top == '{' && c == '}')

                    stack.pop();

                else if (top == '[' && c == ']')

                    stack.pop();

                else

                    return false;

}

                else

{

                    return false;

}

}

}

        return stack.isEmpty();

}

}

27. Remove Element

Easy

4.9K

6.6K

Amazon

Apple

Facebook

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

class Solution {
    public int removeElement(int[] nums, int val) {
        
        ArrayList<Integer> arr  = new ArrayList<>();
        for(int i=0;i<nums.length; i ++)
        {
            if(nums[i]!=val)
            {
                arr.add(nums[i]);
            }


        }

        for(int i=0;i<nums.length;i++)
        {
            if(i > arr.size()-1 )
            {

            }
            else
            {
                nums[i] = arr.get(i);
            }
        }

        return arr.size();

    }
}

118. Pascal's Triangle

Easy

8.7K

288

Amazon

Adobe

Bloomberg

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

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

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

Check my solution here - https://leetcode.com/problems/pascals-triangle/solutions/2937768/java-100-beats-all-very-easy/

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        ArrayList<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> first = new ArrayList<>();
        first.add(1);
        ArrayList<Integer> second = new ArrayList<>();
        second.add(1);
        second.add(1);

        res.add(first);
        if(numRows==1)
        {
            return res;
        }
        res.add(second);
        if(numRows==2)
        {
            return res;
        }
        ArrayList<Integer> third = new ArrayList<>();
        third.add(1);
        third.add(2);
        third.add(1);
        res.add(third);
        if(numRows==3)
        {
            return res;
        }

        for(int i=3;i<numRows;i++)
        {
            //generate
            ArrayList<Integer> newres =  generate(third);
            res.add(newres);
            third = newres;
        }

        return res;


    }

    public static ArrayList<Integer> generate(List<Integer> list)
    {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(list.get(0));
        for(int i=0;i<list.size()-1;i++)
        {
            arr.add(list.get(i)+list.get(i+1));
        }
        arr.add(list.get(0));
        return arr;
    }
}

121. Best Time to Buy and Sell Stock

Easy

22.1K

696

Amazon

Adobe

Apple

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.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

Solution -

class Solution {
    public int maxProfit(int[] prices) {
        
        //brute force approach - o(n^2)
        /*
        int max =0;
        for(int i=0;i<prices.length-1;i++)
        {
            for(int j=i+1;j<prices.length;j++)
            {
                max = Math.max(max, prices[j] - prices[i]);
            }
        }
        return max;

        */

        //single pass approach
        int lowest_yet = Integer.MAX_VALUE;
        int highest_yet = 0;
        int maxdiff = 0;
        for(int i=0;i<prices.length;i++)
        {
            if(prices[i]<lowest_yet)
            {
                lowest_yet = Math.min(lowest_yet, prices[i]); 
            }
            else 
            {
                maxdiff = Math.max(maxdiff, prices[i]-lowest_yet);
            }
        }
        return maxdiff;

    }

    

}

520. Detect Capital

Easy

2.9K

427

Google

Amazon

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".

Given a string word, return true if the usage of capitals in it is right.

Example 1:

Input: word = "USA"
Output: true

Example 2:

Input: word = "FlaG"
Output: false

Constraints:

1 <= word.length <= 100
word consists of lowercase and uppercase English letters.

Solution -

class Solution {
    public boolean detectCapitalUse(String word) {

        
        int c=0,ng=0;
        for(int i=0;i<word.length();i++)
        {
            if(Character.isUpperCase(word.charAt(i)))
            {
                c +=1;
            }
            else
            {
                ng+=1;
            }

        }
        if(c==word.length())
        {
            return true;
        }
        if(ng==word.length())
        {
            return true;
        }
        
        
        for(int i=0;i<word.length();i++)
        {
            if(i==0)
                {
                    if(Character.isUpperCase(word.charAt(i)))
                    {
                        continue;
                    }
                    else
                    {
                        return false;
                    }
                }
            if(Character.isUpperCase(word.charAt(i)))
            {
                
                if(i!=0 && word.charAt(i-1) == ' ')
                {
                    return true;
                }
                else
                {
                    return false;
                }

            }
        }

        return true;

    }
}





200. Number of Islands
Medium
18.8K
420
Amazon
Bloomberg
Google
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
 
Example 1:
Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
 
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
Accepted
2.1M
Submissions
3.6M
Acceptance Rate
56.8%

class Solution {
    public int numIslands(char[][] grid) {
        
        if(grid.length==0 || grid[0].length==0)
        {
            return 0;
        }

        int res =0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]=='1')
                {
                    res = res+1;
                    recrusive_dfs(grid, i,j);
                }
                
            }
        }
        return res;

    }

    public static void recrusive_dfs(char[][] grid , int row, int column)
    {
        if(row<0 || column<0 || row>=grid.length || column>= grid[0].length || grid[row][column]=='0')
        {
            return;
        }

        grid[row][column] = '0';
        recrusive_dfs(grid, row-1, column);
        recrusive_dfs(grid, row, column-1);
        recrusive_dfs(grid, row+1, column);
        recrusive_dfs(grid, row, column+1);
    }
}

Such a Dummy Programmer

Pages

Thursday 30 March 2023

GPT4ALL - A new LLaMa (Large Language Model)

Wednesday 30 November 2022

Leetcode my personal best solutions

Solution -

GPT4ALL - A new LLaMa (Large Language Model)