Word Search - LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Java Solution :

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null)
            return true;
        for(int i =0 ; i < board.length; i++){
            for(int j=0; j < board[i].length ; j++){
                if(board[i][j] == word.charAt(0) && dfs(i,j,0,word,board))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(int i ,int j , int count , String word, char[][] board){
        
        if(count == word.length())
            return true;
        
        if(i<0 || j<0 || i >= board.length || j >= board[i].length || board[i][j] != word.charAt(count))
              return false;
        
        char temp = board[i][j];
        board[i][j] = ' ';
        boolean found = dfs(i+1,j,count+1,word,board) || dfs(i-1,j,count+1,word,board) || dfs(i,j+1,count+1,word,board) ||           dfs(i,j-1,count+1,word,board);
        board[i][j] = temp;
        
        return found;
    }
}

Word Search - LeetCode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Java Solution :

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board == null || word == null)
            return true;
        for(int i =0 ; i < board.length; i++){
            for(int j=0; j < board[i].length ; j++){
                if(board[i][j] == word.charAt(0) && dfs(board,i,j,0,word))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board,int i , int j, int count,String word){
        if(count == word.length())
            return true;
        
        if(i<0 || i >=board.length || j<0 || j>= board[i].length || board[i][j] != word.charAt(count) ){
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = ' ';
        boolean found = dfs(board,i+1,j,count+1,word) || dfs(board,i-1,j,count+1,word) || dfs(board,i,j+1,count+1,word) || dfs(board,i,j-1,count+1,word);
        board[i][j]= temp;
        
        return found;
    }
}

Convert Sorted Array to Binary Search Tree - LeetCode

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Java Solution :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length==0)
            return null;
       
        return constructarraytobst(nums,0,nums.length-1);  
    }
    
    public TreeNode constructarraytobst(int[] nums , int left , int right){
        if(left > right)
          return null;
        
        int mid = left + (right-left)/2;
        TreeNode current = new TreeNode(nums[mid]);
        current.left = constructarraytobst(nums,left,mid-1);
        current.right = constructarraytobst(nums,mid+1,right);
        return current;
    }
}

Linked List Cycle - LeetCode

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Java Solution 1:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)
            return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null )
                return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

Java Solution 2:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodeSeen = new HashSet<>();
        while (head != null){
            if(nodeSeen.contains(head))
                return true;
            else
                nodeSeen.add(head);
            head = head.next;
        }
        return false;
    }
}

Palindrome Linked List - LeetCode

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        ListNode prev = new ListNode(head.val);
        ListNode dummy = head;
        while(dummy.next != null){
            ListNode temp = new ListNode(dummy.next.val);
            temp.next = prev;
            prev = temp;
            dummy = dummy.next;
        }
        
        ListNode last = prev;
        ListNode first = head;
        while(first!=null && last!=null){
            if(first.val == last.val){
                first = first.next;
                last = last.next;
            }else{
                return false;
            }
            
        }
        return true;
            
    }
}

Remove Nth Node From End of List - LeetCode

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null)
            return head;
        ListNode dummy = head;
        ListNode first = new ListNode(0);
        first.next = head;
        int size = 0;
        while (dummy != null){
            size++;
            dummy = dummy.next;
        }
        int k = size-n;
        if(k < 0)
            return null;
        dummy = first;
        while(k > 0){
            dummy = dummy.next;
            k--;
        }
        
        dummy.next = dummy.next.next;
        
        return first.next;   
    }
}

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;
    }
}