DEV Community: Vaishnvee Shinde

LeetCode - Contains Duplicate

Vaishnvee Shinde — Fri, 08 Jul 2022 10:51:42 +0000

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

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

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

Constraints:

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution:

class Solution {
    public boolean containsDuplicate(int[] no) {
         if(no==null || no.length==0)
        return false;

    HashSet<Integer> set = new HashSet<Integer>();
    for(int i: no){
        if(!set.add(i)){
            return true;
        }
    }

    return false;

    }
}

Fore more solutions LeetCode

LeetCode - First Bad Version

Vaishnvee Shinde — Thu, 07 Jul 2022 08:29:55 +0000

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:
Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.

Example 2:
Input: n = 1, bad = 1 Output: 1

Constraints:
1 <= bad <= n <= 231 - 1

Solution:

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int backword = 1;
        int forword = n;
        while(backword <= forword) {
            int mid = backword + (forword - backword) / 2;
            if(!isBadVersion(mid)) {
                backword = mid + 1;
            }else {
                forword = mid - 1;
            }
        }
        return backword;

    }
}

For More Solutions Visit: Leetcode

Leet Code - Binary Search

Vaishnvee Shinde — Thu, 07 Jul 2022 08:04:38 +0000

Problem Statement:
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index.
Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

Solution:

class Solution {
    public int search(int[] nums, int t) {
        return bsearch(nums,t,0,nums.length-1);
    }
    public int bsearch(int []nums, int t, int l, int high)
    {
        if(high<l)
            return -1;
        int mid = l+(high-l)/2;
        if(nums[mid]==t)
            return mid;
        if(nums[mid]>t)
            return bsearch(nums,t,l,mid-1);
        return bsearch(nums,t,mid+1,high);
    }
}

For More Solutions Visit: Leetcode

Leet Code - Remove Duplicates from Sorted Array

Vaishnvee Shinde — Sun, 19 Dec 2021 12:10:18 +0000

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

Java Solution -

import java.util.*;

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

    }
}

Palindrome Number

Vaishnvee Shinde — Sun, 12 Dec 2021 13:02:41 +0000

**Given an integer x, return true if x is palindrome integer.
**
An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

**Example 1:**

Input: x = 121
Output: true
**Example 2:**

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
**Example 3:**

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
**Example 4:**

Input: x = -101
Output: false


**Constraints:**

-231 <= x <= 231 - 1

Solution :
Java Code :

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        int number = x;
        int reverse = 0;
        while (number > 0) {
            reverse = reverse * 10 + number % 10;
            number /= 10;
        }
        return x == reverse;

    }
}

Leet Code Soltion - Roman to Integer

Vaishnvee Shinde — Sun, 12 Dec 2021 12:58:17 +0000

**Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000**
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.

**Example 1:**

Input: s = "III"
Output: 3
**Example 2:**

Input: s = "IV"
Output: 4
**Example 3:**

Input: s = "IX"
Output: 9
**Example 4:**

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
**Example 5:**

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

**Constraints:**

1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Solution :
Java Code :

class Solution {
    public int romanToInt(String S) {
        int ans = 0, num = 0;
        for (int i = S.length()-1; i >= 0; i--) {
            switch(S.charAt(i)) {
                case 'I': num = 1; break;
                case 'V': num = 5; break;
                case 'X': num = 10; break;
                case 'L': num = 50; break;
                case 'C': num = 100; break;
                case 'D': num = 500; break;
                case 'M': num = 1000; break;
            }
            if (4 * num < ans) ans -= num;
            else ans += num;
        }
        return ans;
    }
}

LeetCode - Height Checker Solution

Vaishnvee Shinde — Fri, 10 Dec 2021 09:13:47 +0000

`A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].`

**Example 1:**

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
heights:  [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.

**Example 2:**

Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights:  [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.
Example 3:

Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights:  [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.


**Constraints:**

1 <= heights.length <= 100
1 <= heights[i] <= 100

SOLUTION :
Python Code:

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        count = 0
        for i, (height, expect) in enumerate(zip(heights, expected)):
            if height != expect:
                count +=1
        return count

Python 3.10 Feature

Vaishnvee Shinde — Fri, 16 Jul 2021 09:41:51 +0000

1. Current Problem

With the current Python version, if you want to use type hints for
function that has a parameter which can recive value of different
types, you had to use Union type.

Something like this:

def some_funcion(flexible_parameter: Union[int, string]) -> Union[int, string]: return flexible_parameter

2. Solution Python 3.10 Feature

It introduces new union operand – |. What this operand says is that certain parameter can be either Type 1 either Type 2.
Now, the previous function can be written like this:

def some_funcion(flexible_parameter: int | string) -> int |
string: return flexible_parameter