💡 Interview Approach for Beginners - Clean Code
\n\uD83D\uDCA1Warning []\nIf you know LIS ( Longest Increasing Subsequence ), \nplease don\'t watch this blog just try to think how can you map that\nlogic here
\n```\uD83D\uDCA1Warning []\nIf you know LIS ( Longest Increasing Subsequence ), \nplease don\'t watch this blog just try to think how can you map that\nlogic here. Although in this blog It\'s first and last time I\'m\nmentioning LIS.\n```\n\n### Youtube Solution ( In Hindi Language Only )\nhttps://www.youtube.com/watch?v=0EAv6OKEZSk&ab_channel=CSIITIAN\n\n## Common Sense\nIn Each group atleast one element would be present, so for size 1 we can have n no. of groups.\n\nNow let\'s make some sense, how would you add a number in the group\nGroup: [1, 3, 6]\nand you have 9, would you be able to add ?\nOf Course not why because 9 would not be divisble by 6.\n\nWhat about 12 ? Yes you can add 12.\n\n## Observation to Add New Number\nNow one more thing to observe here is If I just divide the newly (to be) added number by the maximum element of my group I can make sure the whole group is divided. ( Because the group\'s LCM is the maximum number )\n\n### Can I add number less than the maximum number in group ?\nWell yes ! Let\'s see\nGroup: [1, 4, 8]\nand now can I add 2 here ? yes ! Now new Group would be [1, 2, 4, 8]\n\nSo I have to handle two things, \n1. If the number is greater or equal to maximum of group, then it should be divisible by maximum.\n2. If the number is less than maximum of group, it should divide all the group members.\n\nWe can see that in first point, It is much easy to add I just need to know maximum but in second point I need to traverse the whole group to be able to add new element.\n\n## What If Say, I Can handle both in First Point itself\nPreviously we have seen two points by which we can add new number to a group.\nBut What if I always make sure that I add new number using first point only. I mean what if I always make sure that the number I am adding is always greater than group ?\n\nTake a Pause and Think about it , How can we do it ?\n\nOkay, so basically I will sort the array to make sure the element which I am going to add is always greater.\n\nNow I don\'t need to know the group.\n\nSo for current element, I can check all the previous and check divisibility and if it is divisble then it can be added to group so I will increase the group size by 1.\n\nNow I know the size, but here I also need to know the group element, So I also keep track of the element. So whenever I increase the group size I will add the previous element. So that I can backtrack the origin of the group. ( Group\'s starting point would be marked as -1 )\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the Array ( ascending order )\n2. For Each Element traverse the previous element\n3. If element is divisible by any previous element it means it can be part of that group by we also need to make sure it is part of the group with maximum size, So if we found any bigger group we will add it to that group\n4. If we update the group size, it means we have added new element I will update my previous of the current element with group\'s maximum till now ( before adding )\n5. I will also track the index of the last element added in the biggest group\n6. Now I will backtraverse from that maximum index ( defined in previous point ) using my previous element array and one by one add into my result list\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n       \n        Arrays.sort(nums);\n        int n = nums.length;\n       \n        int[] groupSize = new int[n];\n        int[] prevElement = new int[n];\n        int maxIndex = 0;\n\n        for(int i=0;i<n;i++) {\n            groupSize[i] = 1;\n            prevElement[i] = -1;\n            for(int j=0;j<i;j++) {\n                if(nums[i]%nums[j] == 0) {\n                    if(groupSize[i] < 1 + groupSize[j]) {\n                        groupSize[i] = 1 + groupSize[j];\n                        prevElement[i] = j;\n                    }\n                }\n            }\n            if(groupSize[i] > groupSize[maxIndex]) {\n                maxIndex = i;\n            }\n        }\n\n        List<Integer> result = new ArrayList();\n        while(maxIndex != -1) {\n            result.add(0, nums[maxIndex]);\n            maxIndex = prevElement[maxIndex];\n        }\n\n        return result;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n        vector<int> groupSize(n, 1), prevElement(n, -1);\n        int maxIndex = 0;\n\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < i; ++j) {\n                if (nums[i] % nums[j] == 0 && groupSize[i] < groupSize[j] + 1) {\n                    groupSize[i] = groupSize[j] + 1;\n                    prevElement[i] = j;\n                }\n            }\n            if (groupSize[i] > groupSize[maxIndex]) {\n                maxIndex = i;\n            }\n        }\n\n        vector<int> result;\n        for (int i = maxIndex; i != -1; i = prevElement[i]) {\n            result.insert(result.begin(), nums[i]);\n        }\n        return result;\n    }\n};\n```\n```Kotlin []\nfun largestDivisibleSubset(nums: IntArray): List<Int> {\n    nums.sort()\n    val n = nums.size\n    val groupSize = IntArray(n) { 1 }\n    val prevElement = IntArray(n) { -1 }\n    var maxIndex = 0\n\n    for (i in nums.indices) {\n        for (j in 0 until i) {\n            if (nums[i] % nums[j] == 0 && groupSize[i] < groupSize[j] + 1) {\n                groupSize[i] = groupSize[j] + 1\n                prevElement[i] = j\n            }\n        }\n        if (groupSize[i] > groupSize[maxIndex]) {\n            maxIndex = i\n        }\n    }\n\n    val result = mutableListOf<Int>()\n    var i = maxIndex\n    while (i != -1) {\n        result.add(0, nums[i])\n        i = prevElement[i]\n    }\n    return result\n}\n```\n```Python []\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        n = len(nums)\n        groupSize = [1] * n\n        prevElement = [-1] * n\n        maxIndex = 0\n\n        for i in range(n):\n            for j in range(i):\n                if nums[i] % nums[j] == 0:\n                    if groupSize[i] < 1 + groupSize[j]:\n                        groupSize[i] = 1 + groupSize[j]\n                        prevElement[i] = j\n            if groupSize[i] > groupSize[maxIndex]:\n                maxIndex = i\n\n        result = []\n        while maxIndex != -1:\n            result.insert(0, nums[maxIndex])\n            maxIndex = prevElement[maxIndex]\n\n        return result\n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @return {number[]}\n */\nvar largestDivisibleSubset = function(nums) {\n    nums.sort((a, b) => a - b);\n    const n = nums.length;\n    const groupSize = new Array(n).fill(1);\n    const prevElement = new Array(n).fill(-1);\n    let maxIndex = 0;\n\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < i; j++) {\n            if (nums[i] % nums[j] === 0 && groupSize[i] < groupSize[j] + 1) {\n                groupSize[i] = groupSize[j] + 1;\n                prevElement[i] = j;\n            }\n        }\n        if (groupSize[i] > groupSize[maxIndex]) {\n            maxIndex = i;\n        }\n    }\n\n    const result = [];\n    for (let i = maxIndex; i !== -1; i = prevElement[i]) {\n        result.unshift(nums[i]);\n    }\n\n    return result;\n};\n```\n```Rust []\nimpl Solution {\n    pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {\n        let mut nums = nums;\n        nums.sort();\n        let n = nums.len();\n        let mut group_size = vec![1; n];\n        let mut prev_element = vec![-1; n];\n        let mut max_index = 0;\n\n        for i in 0..n {\n            for j in 0..i {\n                if nums[i] % nums[j] == 0 && group_size[i] < group_size[j] + 1 {\n                    group_size[i] = group_size[j] + 1;\n                    prev_element[i] = j as i32;\n                }\n            }\n            if group_size[i] > group_size[max_index] {\n                max_index = i;\n            }\n        }\n\n        let mut result = Vec::new();\n        let mut i = max_index as i32;\n        while i != -1 {\n            result.insert(0, nums[i as usize]);\n            i = prev_element[i as usize];\n        }\n        result\n    }\n}\n```\n```Go []\nfunc largestDivisibleSubset(nums []int) []int {\n    sort.Ints(nums)\n    n := len(nums)\n    groupSize := make([]int, n)\n    prevElement := make([]int, n)\n    maxIndex := 0\n\n    for i := 0; i < n; i++ {\n        groupSize[i] = 1\n        prevElement[i] = -1\n        for j := 0; j < i; j++ {\n            if nums[i]%nums[j] == 0 && groupSize[j]+1 > groupSize[i] {\n                groupSize[i] = groupSize[j] + 1\n                prevElement[i] = j\n            }\n        }\n        if groupSize[i] > groupSize[maxIndex] {\n            maxIndex = i\n        }\n    }\n\n    var result []int\n    for i := maxIndex; i != -1; i = prevElement[i] {\n        result = append([]int{nums[i]}, result...)\n    }\n    return result\n}\n```\n\nThat\'s it guys !!!\n\n## If you really come this far, please upvoted it !\n\n---\n### Connect via\n#### [1. Instagram](https://www.instagram.com/cs_iitian/) ( Follow )\n#### [2. Facebook Page](https://www.facebook.com/cs.iitian)\n#### [3. Twitter](https://twitter.com/cs_iitian)\n#### [4. Blog](https://csiitian.blog/) ( Subscribe to news letter )\n#### [5. Medium](https://medium.com/@csiitian)\n#### [6. Youtube](https://www.youtube.com/channel/UCuxmikkhqbmBOUVxf-61hxw) ( Like, Share & Subscribe )\n#### [7. Leetcode](https://leetcode.com/cs_iitian/)
['Array', 'Math', 'Dynamic Programming', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'Kotlin', 'JavaScript']