[LeetCode] Split Linked List in Parts

Problem: Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Constraints:

• The number of nodes in the list is in the range [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

Approach: It's a straight forward problem to solve. Please have a look at implementation to understand the approach.

Implementation in C#:

    public ListNode[] SplitListToParts(ListNode head, int k) 

    {

        ListNode[] result = new ListNode[k];

        int countOfNodes = this.Count(head);

        int groupSize = countOfNodes / k;

        int extraNodes = countOfNodes % k;

        ListNode node = head;

        for (int i = 0; i < k && node != null; ++i)

        {

            result[i] = node;

            for (int j = 1; j < groupSize + (extraNodes > 0 ? 1 : 0); ++j)

            {

                node = node.next;

            }

            ListNode nextNode = node.next;

            // break the link

            node.next = null;

            node = nextNode;

            --extraNodes;

        }        

        return result;

    }

    

    private int Count(ListNode head)

    {

        int count = 0;

        ListNode node = head;

        while (node != null)

        {

            ++count;

            node = node.next;

        }

        return count;

    }

Complexity: O(n)

[LeetCode] Partition to K Equal Sum Subsets

Problem: Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Example:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Input: nums = [1,2,3,4], k = 3
Output: false

Approach: First we will check if SUM(nums) mod k is 0 or not. If not then we can safely return false. 

Otherwise we have a target_sum which SUM(nums) / k. We just need to find k subsets of nums whose sum is k. This is a backtracking problem. You can understand the logic by just looking at the code.

Implementation in C#:

    public bool CanPartitionKSubsets(int[] nums, int k) 

    {

        int sum = 0;

        for (int i = 0; i < nums.Length; ++i)

        {

            sum += nums[i];

        }

        // Impossible case

        if (sum % k != 0)

        {

            return false;

        }

        int targetSum = sum / k;

        bool[] visited = new bool[nums.Length];

        return KPartitionsPossible(nums, k, targetSum, 0, 0, visited);

    }

    

    private bool KPartitionsPossible(

        int[] nums,

        int k, 

        int targetSum, 

        int currSum,

        int index,

        bool[] visited)

    {

        // All the subsets found, return true.

        if (k == 0)

        {

            return true;

        }

        // Get 1 more subset, now find k - 1 subsets

        if (currSum == targetSum)

        {

            return KPartitionsPossible(nums, k - 1, targetSum, 0, 0, visited);

        }

        for (int i = index; i < nums.Length; ++i)

        {

            if (!visited[i] && currSum + nums[i] <= targetSum)

            {

                visited[i] = true;

                // If true then done return true.

                if (KPartitionsPossible(nums, k, targetSum, currSum + nums[i], i + 1, visited))

                {

                    return true;       

                }

                visited[i] = false;

            }

        }        

        return false;

    }

Complexity: O(k * 2 ^ n)

[LeetCode] N-th Tribonacci Number

Problem: The Tribonacci sequence Tn is defined as follows: 

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Input: n = 25
Output: 1389537

Constraints:

• 0 <= n <= 37
• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Approach: The problem is just like finding nth fibonacci number. Here we just need to add 3 previous numbers. That's all!

Implementation in C#:

    public int Tribonacci(int n)

    {        

        if (n <= 1)

        {

            return n;

        }

        if (n == 2)

        {

            return 1;

        }

        int t0 = 0, t1 = 1, t2 = 1;

        for (int i = 3; i <= n; ++i)

        {

            int t = t0 + t1 + t2;

            t0 = t1;

            t1 = t2;

            t2 = t;

        }

        return t2;

    }

Complexity: O(n)

[LinkedIn] Shortest Word Distance

Problem: Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:

Input: words = ["practice","makes","perfect","coding","makes"], word1 = "coding", word2 = "practice"
Output: 3
Explanation: IndexOf("coding") - IndexOf("practice") = 3 - 0 = 3

Input: words = ["practice","makes","perfect","coding","makes"], word1 = "makes", word2 = "coding"
Output: 1
Explanation: There are two places where "makes" is present in the array which is 1 and 4. The index of "coding" is 3 so the differences are 3 - 1 = 2 and 4 - 3 = 1. The minimum of theses distances (2, 1) is 1.

Constraints:

• word1 is not equal to word2
• word1 and word2 both are present in the given words array.

Approach: It's a straight forward problem to solve. You can look at the implementation to understand the approach.

Implementation in Java:

    public int shortestDistance(String[] words, String word1, String word2) 

    {

        int indexOfWord1 = -1;

        int indexOfWord2 = -1;

        int minDistance = Integer.MAX_VALUE;

        for (int i = 0; i < words.length; ++i) {

            if (words[i].equals(word1))

            {

                indexOfWord1 = i;

                if (indexOfWord2 != -1) {

                    minDistance = Math.min(minDistance, Math.abs(indexOfWord2 - indexOfWord1));

                }

            }

            if (words[i].equals(word2)) {

                indexOfWord2 = i;

                if (indexOfWord1 != -1) {

                    minDistance = Math.min(minDistance, Math.abs(indexOfWord2 - indexOfWord1));

                }

            }

        }

        return minDistance;

    }

Complexity: O(n)

[Google] Minimize Max Distance to Gas Station

Problem: On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.

Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example:

Input: stations = [1,2,3,4,5,6,7,8,9,10], K = 9
Output: 0.5
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Constraints:

• stations.length will be an integer in range [10, 2000].
• stations[i] will be an integer in range [0, 10^8].
• K will be an integer in range [1, 10^6].
• Answers within 10^-6 of the true value will be accepted as correct.

Approach: We are going to use binary search here. How? What is our sorted array here, it is given as input that is our stations distance array. What is initial left? left is the lowest distance possible which is 0. Now  what is initial right; The right will be the maximum distance possible in the given array which is last station distance - first station distance. 

Now we will take the mid of left and right distance and see how many stations can be placed if we use mid distance. If number of station can be placed is <= k then we know that we can make the distance less so we will make right = mid and otherwise if the stations placed are more than k then we have to make distance more i.e. we need to make left = mid.

In the end we can return left or right.

 

Implementation in Java:

    public double minmaxGasDist(int[] stations, int k) {

        int length = stations.length;

        double left = 0;

        double right = stations[length - 1] - stations[0];

        while (right - left > 1e-6) {

            double mid = left + (right - left) / 2;

            if (isFeasible(stations, k, mid)) {

                right = mid;

            }

            else {

                left = mid;

            }

        }

        return right;

    }

    private boolean isFeasible(int[] stations, int k, double dist) {

        int count = 0;

        for (int i = 1; i < stations.length; ++i) {

            count += (int)((stations[i] - stations[i - 1]) / dist);

        }

        return count <= k;

    }

Complexity: O(nlogD) where D is the difference between station[n-1] and stations[0].

[LeetCode] Break a Palindrome

Problem: Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

Example:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba". Of all the ways, "aaccba" is the lexicographically smallest.

Input: palindrome = "a"
Output: ""
Explanation: There is no way to replace a single character to make "a" not a palindrome, so return an empty string.

Input: palindrome = "aa"
Output: "ab"

Input: palindrome = "aba"
Output: "abb"

Constraints:

• 1 <= palindrome.length <= 1000
• palindrome consists of only lowercase English letters.

Approach: Let's go greedy. We will make the first character 'a' which is not 'a' and in that way we will have a string which is not palindrome and also it will be the smallest string possible. Now what if the string have all 'a'. In that case we can change the last character to 'b'. The only problem with this approach will be if a string has all 'a's except the one character. For example "aba", here if we change the first non 'a' character the string will become "aaa".

To solve this problem we either traverse the whole string to see if now the string has all 'a's  or we can just check the non 'a' character in first half of the string as the string is palindrome, the last half will have the exact same characters. 

 

Implementation in C#:

    public string BreakPalindrome(string palindrome) 

    {

        if(palindrome.Length <= 1)

        {

            return "";

        }        

        char[] palindromeArr = palindrome.ToCharArray();

        for (int i = 0; i < palindromeArr.Length / 2; ++i)

        {

            if (palindromeArr[i] != 'a')

            {

                palindromeArr[i] = 'a';

                return new string(palindromeArr);

             }

        }

        palindromeArr[palindromeArr.Length - 1] = 'b';

        return new string(palindromeArr);

    }

Complexity: O(n)

[LeetCode] Maximum Length of a Concatenated String with Unique Characters

Problem: Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Approach: Basically we need to apply backtracking here. We will try every valid combination and get the length of the largest valid combination here.

Implementation in C#:

    public int MaxLength(IList<string> arr) 

    {

        int maxLength = 0;

        int currLength = 0;

        int[] charsVisited = new int[26];

        MaxLengthRec(arr, 0, ref maxLength, currLength, charsVisited);

        return maxLength;

    }

    

    private void MaxLengthRec(

        IList<string> arr, 

        int currIndex, 

        ref int maxLength, 

        int currLength, 

        int[] charsVisited)

    {

        for (int i = 0; i < 26; ++i)

        {

            if (charsVisited[i] > 1)

            {

                return;

            }

        }

        maxLength = Math.Max(currLength, maxLength);                

        for (int i = currIndex; i < arr.Count; ++i)

        {

            foreach(char ch in arr[i])

            {

                ++charsVisited[ch - 'a'];

            }           

            currLength += arr[i].Length;

            MaxLengthRec(arr, i + 1, ref maxLength, currLength, charsVisited);

            currLength -= arr[i].Length;

            foreach(char ch in arr[i])

            {

                --charsVisited[ch - 'a'];

            }

        }

    }

Complexity: O(2^N)