LeetCode Easy: Remove Duplicates from Sorted Array

An easy level problem on LeetCode - Remove Duplicates from Sorted Array (https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

 

 

 

APPROACH 1:

 

I wrote a quick and easy solution in C++ for this easy level problem some years back - Single pass and O(n), ignoring all duplicates as we go:

class Solution {
public:
    int removeDuplicates(vector& nums) {
        int len = nums.size();
        if (len<=1)
            return len;
        
        int i, top;
        for (i=1, top=1; i<len; i++)
        {
            if (nums[i] != nums[top-1])
                nums[top++] = nums[i];
        }
        
        return top;
    }
};

 

 

 

APPROACH 2:

 

A couple of dys back, I revisited this problem, in Java, but this time, I looked at it and instantly came to my mind, an even more optimised version of it, O(lg m) in time complexity, where, m = number of unique elements in the input list, making use of predicate based binary searching technique to get the last occurrence of a particular element in the left part of the current index:

 

Here’s how the solution goes for it:

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int reducedLen = -1;
        if (nums.length == 0)
            return reducedLen+1;
        
        int pos = 0;
        while (pos < nums.length) {
            pos = getLastOccurenceIdx(nums, pos);
            nums[++reducedLen] = nums[pos];
            pos++;
        }
        
        return reducedLen+1;
    }
    
    private int getLastOccurenceIdx(int[] nums, int firstPos) {
        int min = firstPos;
        int max = nums.length-1;
        while (min < max) {
            int mid = min + (max-min+1)/2;
            if (nums[mid]>nums[firstPos]) {
                max = mid-1;
            } else {
                min = mid;
            }
        }
        return min; 
    }
}

 

 

Do share if better solutions cross your mind!

Happy Coding, until next spree!!

SPOJ: SUBSUMS - Subset Sums

Today I solved the Subset Sums (SUBSUMS) problem on SPOJ. Here's the link: http://www.spoj.com/problems/SUBSUMS

By the name of it, it seems like a classic Dynamic Programming problem, but as soon as you pay attention to the constraints, it soon becomes evident that a DP solution which will most optimally have O(N*W) complexity, where N = number of elements and W= the target sum range's upper bound, will bottleneck at W.

I solved this problem using Meet in the middle technique whereby, I divide the set of input numbers into 2 halves and consider sums of all subsets in each half (cardinality 2^17 in each set, which can be pretty easily generated using brute-force recursion), to find the subset-duos (containing one subset from each half) who sum up to fall in the given range. The count of such possible subset-duos gives us our solution. My solution also involves putting binary search and recursion into use.

Here's my accepted(https://www.spoj.com/status/SUBSUMS,chandniverma/) solution code:

  

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.function.BiPredicate;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		int arr[] = new int[N];
		for (int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		
		System.out.println(getCountOfSubsets(arr, A, B));
	}

	private static long getCountOfSubsets(int[] arr, int a, int b) {
		Integer[] firstSubsetSums = getSubsetSums(arr, 0, arr.length/2);
		Integer[] secondSubsetSums = getSubsetSums(arr, arr.length/2+1, arr.length-1);
		Arrays.sort(secondSubsetSums);
		
		long count = 0;
		for(int i=0; i<firstSubsetSums.length; i++) {
			int p = findLastIdxWithFalsePredicate(secondSubsetSums, a-firstSubsetSums[i], (sum, mark)->sum>=mark);
			int q = findLastIdxWithFalsePredicate(secondSubsetSums, b-firstSubsetSums[i], (sum, mark)->sum>mark);
			count += (q-p);
		}
		
		return count;
	}

	private static int findLastIdxWithFalsePredicate(Integer[] sums, int val, BiPredicate<Integer, Integer> pred) {
		int min = 0;
		int max = sums.length-1;
		while (min<max) {
			int mid = min + (max-min+1)/2;
			if (pred.test(sums[mid], val)) {
				max = mid-1;
			} else {
				min = mid;
			}
		}
		if (pred.test(sums[min], val))
			return -1;
		return min;
	}

	private static Integer[] getSubsetSums(int[] arr, int st, int end) {
		List<Integer> sums = new ArrayList<>();
		generateSubsetSumsRecur(arr, st, end, st, 0, sums);
		return sums.toArray(new Integer[0]);
	}

	private static void generateSubsetSumsRecur(int[] arr, int st, int end, int index, int runningSum, List<Integer> sums) {
		if (index == end+1) {
			sums.add(runningSum);
			return;
		}
		
		generateSubsetSumsRecur(arr, st, end, index+1, runningSum+arr[index], sums);
		generateSubsetSumsRecur(arr, st, end, index+1, runningSum, sums);
	}
}

 
  

The complexity of the above code is:

O(2^(N/2) + 2^(N/2)*(lg (2^(N/2)))) 

= O(2^(N/2) + 2^(N/2)*N/2) 

= O(N*2^(N/2)) 

Feel free to checkout and let me know your thoughts in the comments below! Do share if you have a better solution in mind!

LeetCode Medium: Count Complete Tree Nodes

Here is one LeetCode Medium level problem (Problem # 222: Count Complete Tree Nodes) which is an actual 2 liner to solve when solved recursively:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

This solution is O(n) in number of nodes in the binary tree and is a generic solution that can be used to solve any binary tree for that matter.

The fact that this is a complete binary tree, brings to my mind another solution approach with O((lg n)^2) solution which I'll share here very soon!

Until next time,

Stay Tuned and Happy Coding!

See ya later!!

LeetCode Problem #441. Arranging Coins

Here is my solution on LeetCode Problem #441. Arranging Coins 

Approach 1: Based on binary search and inequalities

class Solution {
    public int arrangeCoins(int N) {
        long minLevel = 0;
        long maxLevel = N;
        while (minLevel<maxLevel) {
            long midLevel = minLevel + (maxLevel-minLevel+1)/2;
            boolean predicate = ((midLevel*midLevel + midLevel) > (2*(long)N));
            
            if (predicate) {
                maxLevel = midLevel-1;
            }
            else {
                minLevel = midLevel;
            }
        }
        
        if ((minLevel*minLevel + minLevel) > (2*(long)N))
            return -1;
        return (int)minLevel;
    }
}

The time complexity is super-fast: O(lg n) where n is the the input N(the number of coins) and I don't think it can get any faster iteratively.

The only other faster solution I can think of is using SriDharacharya formula to find the roots to inequality:

l^2 + l <= 2*N

where l = last complete level

Do share your thoughts below!

<3
~Take Care

Leetcode Medium - Find Peak Element

Following is my Solution to Problem #162: Find Peak Element. Feel free to discuss and/or add your comments.

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

There's a faster solution that guarantees answer in O(lg(n)) time. It uses Binary Search trick.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        int min = 0;
        int max = nums.length-1;
        while (min<max) {
            int mid = min+ (max-min)/2;
            
            if (nums[mid]<nums[mid+1])
                min = mid+1;
            else
                max = mid;
        }
        
        return min;
    }
}