Wednesday, 30 November 2022

Leetcode my personal best solutions

26. Remove Duplicates from Sorted Array
Easy
9.5K
13.1K
company
Apple
company
Amazon
company
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
company
Amazon
company
Apple
company
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
company
Amazon
company
BlackRock
company
Bloomberg

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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 '()[]{}'.



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
company
Amazon
company
Apple
company
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.

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 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
company
Amazon
company
Adobe
company
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


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
company
Amazon
company
Adobe
company
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
company
Google
company
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
company
Amazon
company
Bloomberg
company
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);
}
}
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

GPT4ALL - A new LLaMa (Large Language Model)

posted 29th March, 2023 - 11:50, GPT4ALL launched 1 hr ago  What if we use AI generated prompt and response to train another AI - Exactly th...