Largest Divisible subset
Problem
Backtracking solution (TLE)
tc : O(2^n)
class Solution {
List<Integer> result =null;
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
get(0,nums,new ArrayList<>());
return result;
}
public void get(int index, int [] nums, List<Integer> l){
if(index == nums.length){
if(result ==null || result.size() < l.size()){
result = new ArrayList<>(l);
}
return;
}
if(l.size() ==0 || nums[index] % l.get(l.size()-1)==0){
l.add(nums[index]);
get(index+1,nums,l);
l.remove(l.size()-1);
}
get(index+1,nums,l);
}
}
2d dp memoization (with index and prev index)
TC: O(n^2), sc: O(n^3) as n^2 for dp array and each cell will store at max n elements + space for recursive stack space which will also be O(n^2)
note: it is always better to use array that map for dp as in map we would have done some hacky stuff to get the key like i+”,”+prev or new Pair(i,prev) but using map will give tle, array dp works fine and succeeds
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
List ap[][] = new List[nums.length][nums.length+1];
for(List a[] : ap) Collections.nCopies(ap.length,null);
return getWithPrevious(0,-1,nums,ap);
}
public List<Integer> getWithPrevious(int i, int prev, int nums[],List dp[][]){
if(i == nums.length) return new ArrayList<>();
if(dp[i][prev+1]!=null) return dp[i][prev+1];
//take
List<Integer> take = new ArrayList<>();
if(prev == -1 || nums[i] % nums[prev] == 0){
take.add(nums[i]);
take.addAll(getWithPrevious(i+1,i,nums,dp));
}
List<Integer> donTake =new ArrayList<>();
donTake.addAll(getWithPrevious(i+1,prev,nums,dp));
List<Integer> res = take.size() > donTake.size() ? take : donTake;
dp[i][prev+1] = res;
return res ;
}
}
1d dp memoization (without prev index)
tc : O(n^2), sc: O(n^2) as we have avoided using 2 dimension but each cell in dp will store at max n elements + space for recursive stack space which will also be O(n^2)
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
List dp[] = new List[nums.length];
List<Integer> result =new ArrayList<>();
for(int i = 0;i< nums.length;i++){
List<Integer> l = topDown(i,nums,dp);
if(l.size() > result.size()) result = l;
}
return result;
}
public List<Integer> topDown(int index ,int nums[],List[] dp){
//base case
if(index == nums.length){
return new ArrayList<>();
}
if(dp[index]!=null) return dp[index];
List<Integer> result = new ArrayList<>();
result.add(nums[index]);// this will be previous
for(int k = index+1;k<nums.length;k++){
if(nums[k] % nums[index] ==0){
List<Integer> temp = new ArrayList<>();
temp.add(nums[index]);
temp.addAll(topDown(k, nums,dp));
if(temp.size() > result.size()){
result = temp;
}
}
}
dp[index]= result;
return result;
}
}
Tabulation
tc: O(n^2), sc : O(n^2) with to recursive stack space
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
List<Integer> result = new ArrayList<>();
List dp[] = new List[nums.length];
///initialization
for(int i = 0;i< nums.length;i++){
dp[i] = new ArrayList<>();
dp[i].add(nums[i]);// smallest possible list that satisfies the condition will be the List having nums[i] atleast
}
for(int index = nums.length-1;index>=0;index--){
for(int k = index+1;k<nums.length;k++){
if(nums[k] % nums[index] ==0){
List<Integer> temp = new ArrayList<>();
temp.add(nums[index]);
temp.addAll(dp[k]);
if(temp.size() > dp[index].size()){
dp[index] = temp;
}
}
}
if(dp[index].size() > result.size()) result = dp[index];
}
return result;
}
}
