Delete Node in a Linked List - LeetCode

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list -- head = [4,5,1,9], which looks like following:

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:

The linked list will have at least two elements.
All of the nodes' values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Longest Common Prefix - LeetCode

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: ["flower","flow","flight"]
Output: "fl"

Example 2:

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

Note:

All given inputs are in lowercase letters a-z.

Java Solution :

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";
        String prefix = strs[0];
        for(int i =1 ; i < strs.length ; i++){
            while(strs[i].indexOf(prefix) != 0){
                prefix = prefix.substring(0,prefix.length()-1);
                if(prefix.isEmpty())
                    return "";
            }
        }
        return prefix;
    }
}

Valid Palindrome - LeetCode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Java Solution :

class Solution {
    public boolean isPalindrome(String s) {
         if(s.length() == 0 || s == null)
             return true;
        int i =0;
        int j = s.length()-1;
        
        while(i < j){
            while(i < j && !Character.isLetterOrDigit(s.charAt(i))){
                i++;
            }
            while(i < j && !Character.isLetterOrDigit(s.charAt(j))){
                j--;
            }
            if(i<j && Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
                return false;
        }
    return true;
    }
}

Plus One - LeetCode

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Java Solution :

class Solution {
    public int[] plusOne(int[] digits) {
        int lastIndex = digits.length-1;
        int carry = 1;
        int[] plusOne = new int[digits.length+1];
        if(digits[lastIndex]<9){
            digits[lastIndex]=digits[lastIndex]+1;
            return digits;
        }else{
            for(int i=digits.length-1;i>=0;i--){
                if(digits[i]==9){
                 digits[i]= (digits[i]+carry);
                 carry = digits[i]/10;
                 digits[i]=digits[i]%10;   
                }
                else{
                    digits[i]=digits[i]+carry; 
                    carry = 0;
            }
            }
            if(carry == 1){
                plusOne[0] = 1;
                for(int i=0;i<digits.length;i++){
                    plusOne[i+1] = digits[i];
                }
                return plusOne;
            }
        }
        return digits;
    }
}

Valid Anagram - LeetCode

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Java Solution :

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;
        int[] tableA = new int[26];
        
        for(int i =0 ; i < s.length() ; i++){
            tableA[s.charAt(i)-'a']++;
        }
        
        for(int i=0;i<t.length(); i++){
            tableA[t.charAt(i)-'a']--;
            if(tableA[t.charAt(i)-'a'] < 0)
                return false;
        }
        return true;
    }
}

Reverse String -LeetCode

Write a function that reverses a string. The input string is given as an array of characters char[].

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

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Java Solution :

class Solution {
    public void reverseString(char[] s) {
        if(s.length == 0 || s == null)
            return;
        int k = s.length;
        for(int i =0 ; i < k/2;i++){
            char temp = s[i];
            s[i] = s[k-i-1];
            s[k-i-1] = temp;
        }
    }
}

Valid Sudoku - LeetCode

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.
• The given board contain only digits 1-9 and the character '.'.
• The given board size is always 9x9.

Java Solution :

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if(board == null || board.length == 0)
            return false;
        HashMap<Integer,Integer> [] rows = new HashMap[9];
        HashMap<Integer,Integer> [] cols = new HashMap[9];
        HashMap<Integer,Integer> [] boxes = new HashMap[9];
        
        for(int i = 0; i < 9 ; i++){
            rows[i] = new HashMap<Integer,Integer>();
            cols[i] = new HashMap<Integer,Integer>();
            boxes[i] = new HashMap<Integer,Integer>();
        }
        int num =0;
        for(int i =0 ; i < 9 ; i++){
            for(int j=0; j < 9; j++){
                char n = board[i][j];
                if(board[i][j] != '.'){
                 num = (int)n;
                int box_index = (i/3)*3 + j/3;
                rows[i].put(num,rows[i].getOrDefault(num,0)+1);
                cols[j].put(num,cols[j].getOrDefault(num,0)+1);
                boxes[box_index].put(num,boxes[box_index].getOrDefault(num,0)+1);
                
                if(rows[i].get(num) > 1 || cols[j].get(num) > 1 || boxes[box_index].get(num) > 1)
                    return false;
            }
        }
        }
        
        return true;
    }
}