LeetCode #5

What I’ve Learned

First, checking inside a array can be simple as playing with two pointers and using original array.

Disclaimer

My LeetCode is free plan. I am posting just the free algorithms for now on. Also, I am using JAVA to code.

27. Remove Element

My Solution

This question was similar to what I’ve solved yesterday, 26. Remove Duplicates from Sorted Array. I’ve changed some of bit and solved. Main algorithm is to check the current and value, adding it to existing nums.

class Solution {
    public int removeElement(int[] nums, int val) {
        int j =0;
        for(int i =0; i<nums.length; i++) {
        	if(nums[i] != val) {
        		nums[j] = nums[i];
        		j++;
        	}
        }
        return j;
    }
}

28. Find the Index of the First Occurrence in a String

My Solution

This question is easy. Finding string inside another string. There is already a method in java. It wasn’t hard to solve.

class Solution {
    public int strStr(String haystack, String needle) {
    	int numb = haystack.indexOf(needle);
    	return numb;
    }
}

35. Search Insert Position

My Solution

I’ve used Stack for this problem. Adding if it’s smaller than target and break when it’s bigger or same. Then it retrieves the result successfully. It works, but I think this is not the answer what leetcode wants. Due to the expression You must write an algorithm with O(log n) runtime complexity., I think it’s binary search. But, I don’t know how.

class Solution {
    public int searchInsert(int[] nums, int target) {
    	Stack<Integer> stack = new Stack<>();
    	int result = 0;
        for(int i =0; i<nums.length; i++) {
        	if(nums[i] < target) {
        		stack.push(nums[i]);
        	} else if(nums[i] > target || nums[i] == target) {
        		break;
        	}
        }
        result = stack.size();
        return result;
    }
}

Solution1

Surprising thing is that there are already binarySearch method in Java. Idea is simple. Checking the medium of the array, if it’s larger, search bottom half and vice versa.
First solution is not using binarySearch method. It’s checking target repeateadly and add start or subtract end.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;

        while (start <= end) {
            int mid = start + (end-start)/2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) end = mid-1;
            else start = mid+1;
        }

        return start;
    }
}

Solution2

This version is using binarySearch. It’s fast.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int ans=Arrays.binarySearch(nums,target);
        if(ans<0){
            return -ans-1;
        }
        return ans;
    }
}