LeetCode Java Solution:- Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 1:

Input: [1,3,5,6], 0
Output: 0

Solution:-

class Solution {
    public int searchInsert(int[] nums, int target) {
   
    int start = 0;
    int end = nums.length - 1;
    int mid = 0 ;
    while(start <= end){
    mid = (start + end)  / 2 ;
   
    if(nums[mid] == target){
    return mid;
    }
    else if(nums[mid] < target){
    start = mid + 1;
    }
    else{
    end = mid - 1;
    }
    }
   
    return start;
       
    }
}

LeetCode Java Solution:- Convert Sorted Array to Binary Search Tree

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

/**
 * 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.length == 0){
            return null;
        }

        return getTreeNode(nums, 0, nums.length -1);
    
        
    }
    
    private TreeNode getTreeNode( int[] nums, int a , int b){
        
        int start = a;
        int end = b ;
        
        if(start > end){
            return null;
        }
        
        int mid = (start +end) / 2 ;
       TreeNode node = new TreeNode(nums[mid]);
        node.left = getTreeNode(nums, start , mid -1);
        
        node.right = getTreeNode(nums, mid+1 , end);
        
        return node;
            
        
        
      
    }

}

LeetCode Java Solution : Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> arr = convertListToArray(head);
        
        return getBInaryTree(arr, 0 , arr.size() -1);
    }
    
    
    
    private List<Integer> convertListToArray(ListNode head){
        List<Integer> arr = new ArrayList<Integer>();
        while(head != null){
            arr.add(head.val);
            head = head.next;
        }
        return arr;
    }
    
    
    private TreeNode getBInaryTree(List<Integer> arr, int start, int end){
        
        if(start > end){
            return null;
        }
        int mid = (start + end) / 2;
            
        TreeNode node = new TreeNode(arr.get(mid));
        node.left = getBInaryTree(arr, start, mid - 1);
        node.right = getBInaryTree(arr, mid + 1 , end);
        
        return node;
        
    }

}

LeetCode - Java Solution Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Solution:-

class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        

        int [] ret = new int[m+n];

        int k = 0 , i = 0 , j = 0;

        while( i < m && j < n){

            if(nums1[i] <= nums2[j]){

                ret[k] = nums1[i];

                i++;

            }

            else{

                ret[k] = nums2[j];

                j++;

            }

            k++; 

        }

        if( i == m && j < n){    

            for(int item = j ; item < n ; item++ ){

             ret[k] = nums2[item];

            System.out.println(ret[k] + " "+ nums2[item]);

                k++;   

            }

        }

        

        if( j == n && i < m){

            for(int item = i ; item < m ; item++ ){

                

                ret[k] = nums1[item];

                k++;

            }

        }

        

        for(int l = 0 ; l < ret.length ; l++){

            nums1[l] = ret[l];

        }

    

    }

}