Leetcode 804. Unique Morse Code Words

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a"maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cab" can be written as "-.-.-....-", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Note:

• The length of words will be at most 100.
• Each words[i] will have length in range [1, 12].
• words[i] will only consist of lowercase letters.

Code (Java):

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        if (words == null || words.length == 0) {
            return 0;
        }
        
        Set<String> morseCodeSet = new HashSet<>();
        
        int ans = 0;
        
        for (String word : words) {
            String morseCode = GetMorseCode(word);
            
            if (!morseCodeSet.contains(morseCode)) {
                morseCodeSet.add(morseCode);
            }
        }
        
        return morseCodeSet.size();
    }
    
    private String GetMorseCode(String word) {
        String[] morseCodeDict = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        String morseCode = "";
        
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            morseCode += morseCodeDict[c - 'a'];
        }
        
        return morseCode;
    }
}

Leetcode 814. Binary Tree Pruning

We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

• The binary tree will have at most 100 nodes.
• The value of each node will only be 0 or 1.

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        
        if (root.val == 1 || root.left != null || root.right != null) {
            return root;
        }
        
        return null;
        
    }
}

Another solution:

Algorithm

We'll use a function containsOne(node) that does two things: it tells us whether the subtree at this nodecontains a 1, and it also prunes all subtrees not containing 1.

If for example, node.left does not contain a one, then we should prune it via node.left = null.

Also, the parent needs to be checked. If for example the tree is a single node 0, the answer is an empty tree.

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the number of nodes in the tree. We process each node once.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This represents the size of the implicit call stack in our recursion.

Leetcode 796. Rotate String

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1:
Input: A = 'abcde', B = 'cdeab'
Output: true

Example 2:
Input: A = 'abcde', B = 'abced'
Output: false

Note:

• A and B will have length at most 100.

Code (Java)

class Solution {
    public boolean rotateString(String A, String B) {
        if (A == null) {
            return B == null;
        }
        
        if (A.length() == 0) {
            return B.length() == 0;
        }
        
        if (A.length() != B.length()) {
            return false;
        }
        
        char[] arrayA = A.toCharArray();
        
        for (int i = 0; i < A.length(); i++) {
            rotate(arrayA);
            String rotatedA = String.valueOf(arrayA);
            if (rotatedA.equals(B)) {
                return true;
            }
        }
        
        return false;
    }
    
    private void rotate(char[] A) {
        char firstCh = A[0];
        for (int i = 1; i < A.length; i++) {
            A[i - 1] = A[i];
        }
        
        A[A.length - 1] = firstCh;
    }
}

Another Solution:

Approach #2: Simple Check [Accepted]

Intuition and Algorithm

All rotations of A are contained in A+A. Thus, we can simply check whether B is a substring of A+A. We also need to check A.length == B.length, otherwise we will fail cases like A = "a", B = "aa".

Complexity Analysis

• Time Complexity: $O(N^2)$, where $N$ is the length of A.
• Space Complexity: $O(N)$, the space used building A+A.

Leetcode 813. Largest Sum of Averages

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

Example:
Input: 
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation: 
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Note:

• 1 <= A.length <= 100.
• 1 <= A[i] <= 10000.
• 1 <= K <= A.length.
• Answers within 10^-6 of the correct answer will be accepted as correct.

Code (Java):

class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int len = A.length;
        
        double[][] dp = new double[len + 1][K + 1];
        double[] prefixSum = new double[len + 1];
        
        for (int i = 1; i <= len; i++) {
            prefixSum[i] = prefixSum[i - 1] + A[i - 1];
            
            // Init dp
            //
            dp[i][1] = prefixSum[i] / i;
        }
        
        for (int k = 2; k <= K; k++) {
            for (int i = k; i <= len; i++) {
                for (int j = k - 1; j < i; j++ ) {
                   dp[i][k] = Math.max(dp[i][k], dp[j][k - 1] + (prefixSum[i] - prefixSum[j]) / (i - j));
                }
            }
        }
        
        return dp[len][K];
    }
}

Leetcode 801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i].  Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing.  (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  It is guaranteed that the given input always makes it possible.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

Note:

• A, B are arrays with the same length, and that length will be in the range [1, 1000].
• A[i], B[i] are integer values in the range [0, 2000].

A Wrong Solution (Greedy):

The first idea is to use greedy algorithm. Since we know that there must be at least one solution, we just scan the array A. If we found the sequence is not strictlly increasing, we just swap with B. Then we also need to scan the array B again since B may not be increasing. 

Code (Java):

class Solution {
    public int minSwap(int[] A, int[] B) {
        int numOfSwaps = 0;
        
        // First scan of A
        //
        for (int i = 1; i < A.length; i++)
        {
            if (A[i] <= A[i - 1])
            {
                swap(A, B, i);
                numOfSwaps++;
            }
        }
        
        // Second scan of B to make sure we did not miss anything
        //
        for (int i = 1; i < B.length; i++)
        {
            if (B[i] <= B[i - 1])
            {
                swap(A, B, i);
                numOfSwaps++;
            }
        }
        
        return numOfSwaps;
    }
    
    private void swap(int[] A, int[] B, int index)
    {
        int temp = A[index];
        A[index] = B[index];
        B[index] = temp;
    }
}

Analysis:
So why the solution is wrong? One example is

Input:[0,4,4,5,9] [0,1,6,8,10]

Output:2

Expected:1

So we only need to swap A[1] with B[1]. That's the miminum number of swaps.
It tells us greedy algorithm does not work most of the time.


Correct Solution:
This problem is a classic sackpack problem. For each pair of A[i] and B[i], we can choose to swap or not. So we define two dp arrays, keep[i] means if we don't swap A[i] and B[i], what's the min number of swaps. swap[i] is the min number of swaps if we swap A[i] and B[i].

Since the problem guarantees that there is a valid solution. We only need to consider two cases:

1. A[i] > A[i -1] && B[i] > B[i - 1],
if we choose to keep, we should keep the previous i - 1 elements. So keep[i] = keep[i - 1]
If we choose to swap, in order to maintain the sequencing order, we must swap the previous i - 1 th element. So swap[i] = swap[i - 1] + 1;

2. A[i] > B[i - 1] && B[i] > A[i - 1]
If we choose to keep, keep[i] = Math.min(keep[i], swap[i - 1])
If we choose to swap, swap[i] = Math.min(swap[i], keep[i - 1] + 1)

3. For other cases such as A[i] < B[i - 1] we don't need to consider since we gurantee there will be a solution.

Code (Java):

class Solution {
    public int minSwap(int[] A, int[] B) {
        int len = A.length;
        int[] keep = new int[len];
        int[] swap = new int[len];
        
        // Init for max
        //
        for (int i = 0; i < len; i++)
        {
            keep[i] = Integer.MAX_VALUE;
            swap[i] = Integer.MAX_VALUE;
        }
        
        keep[0] = 0;
        swap[0] = 1;
        
        for (int i = 1; i < len; i++)
        {
            if (A[i] > A[i - 1] && B[i] > B[i - 1])
            {
                keep[i] = keep[i - 1];
                swap[i] = swap[i - 1] + 1;
            }
            
            if (A[i] > B[i - 1] && B[i] > A[i - 1])
            {
                keep[i] = Math.min(keep[i], swap[i - 1]);
                swap[i] = Math.min(swap[i], keep[i - 1] + 1);
            }
        }
        
        return Math.min(keep[len - 1], swap[len - 1]);
    }
}

Leetcode 806. Number of Lines To Write String

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of 'a', widths[1] is the width of 'b', ..., and widths[25] is the width of 'z'.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

Example :
Input: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation: 
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.

Example :
Input: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
Output: [2, 4]
Explanation: 
All letters except 'a' have the same length of 10, and 
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.

Note:

• The length of S will be in the range [1, 1000].
• S will only contain lowercase letters.
• widths is an array of length 26.
• widths[i] will be in the range of [2, 10].

Code (Java):

class Solution {
    public int[] numberOfLines(int[] widths, String S) {
        int cLines = 1;
        int cChCurrentLine = 0;
        
        for (int i = 0; i < S.length(); i++)
        {
            char c = S.charAt(i);
            cChCurrentLine += widths[c - 'a'];
            if (cChCurrentLine > 100)
            {
                cLines++;
                cChCurrentLine = widths[c - 'a'];
            }
        }
        
        int[] ans = new int[2];
        ans[0] = cLines;
        ans[1] = cChCurrentLine;
        
        return ans;
    }
}

Leetcode 812: Largest Triangle Area

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

Notes:

• 3 <= points.length <= 50.
• No points will be duplicated.
•  -50 <= points[i][j] <= 50.
• Answers within 10^-6 of the true value will be accepted as correct.

Analysis:

Solution:

class Solution {
    public double largestTriangleArea(int[][] points) {
        double area = 0.0;
        
        for (int p1 = 0; p1 < points.length; p1++) {
            for (int p2 = p1 + 1; p2 < points.length; p2++) {
                for (int p3 = p2 + 1; p3 < points.length; p3++) {
                    area = Math.max(area, getArea(points[p1], points[p2], points[p3]));
                }
            }
        }
        
        return area;
    }
    
    private double getArea(int[] p1, int[] p2, int[] p3) {
        return Math.abs((p2[0] - p1[0]) * (p3[1] - p1[1]) - 
                       0.5 * (p2[0] - p1[0]) * (p2[1] - p1[1]) - 
                       0.5 * (p3[0] - p1[0]) * (p3[1] - p1[1]) -
                       0.5 * (p2[0] - p3[0]) * (p3[1] - p2[1]));
    }
}

Leetcode 811. Subdomain Visit Count

A website domain like "discuss.leetcode.com" consists of various subdomains. At the top level, we have "com", at the next level, we have "leetcode.com", and at the lowest level, "discuss.leetcode.com". When we visit a domain like "discuss.leetcode.com", we will also visit the parent domains "leetcode.com" and "com" implicitly.

Now, call a "count-paired domain" to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be "9001 discuss.leetcode.com".

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

Example 1:
Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation: 
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:
Input: 
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: 
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation: 
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

• The length of cpdomains will not exceed 100. 
• The length of each domain name will not exceed 100.
• Each address will have either 1 or 2 "." characters.
• The input count in any count-paired domain will not exceed 10000.
• The answer output can be returned in any order.

Solution (Java):

Code (Java):

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> ans = new ArrayList<>();
        
        if (cpdomains == null || cpdomains.length == 0)
        {
            return ans;
        }
        
        Map<String, Integer> cpDomainsMap = new HashMap<>();
        
        for (String cpdomain : cpdomains)
        {
            String delimiter = "[. ]+";
            String[] domainTokens = cpdomain.split(delimiter);
            int hitCount = Integer.parseInt(domainTokens[0]);
            
            String subdomain = null;
            for (int tokenIndex = domainTokens.length - 1; tokenIndex > 0; tokenIndex--)
            {
                subdomain = getSubdomain(subdomain, tokenIndex, domainTokens);
                
                if (cpDomainsMap.containsKey(subdomain))
                {
                    cpDomainsMap.put(subdomain, cpDomainsMap.get(subdomain) + hitCount);
                }
                else
                {
                    cpDomainsMap.put(subdomain, hitCount);
                }
            }
        }
        
        // Iterate hashmap and return results
        //
        Iterator it = cpDomainsMap.entrySet().iterator();
        while (it.hasNext())
        {
            Map.Entry pair = (Map.Entry)(it.next());
            String output = pair.getValue() + " " + pair.getKey();
            ans.add(output);
            it.remove(); // avoid concurrent modification ex
        }
        
        return ans;
    }
    
    private String getSubdomain(String subdomain, int tokenIndex, String[] domainTokens)
    {
        if (tokenIndex == domainTokens.length - 1)
        {
            subdomain = domainTokens[tokenIndex];
        }
        else
        {
            subdomain = domainTokens[tokenIndex] + "." + subdomain;
        }
        
        return subdomain;
    }
}

Leetcode: 319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

Code (Java):

public class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

Leetcode: 320. Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Understand the problem:
A classic dfs + backtracking problem. A trick here is if we've already abbrivate part of a word, we must jump at least a character.

Code (Java):

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> result = new ArrayList<>();

        result.add(word);
        generateHelper(0, word, result);
        
        return result;
    }
    
    private void generateHelper(int start, String s, List<String> result) {
        if (start >= s.length()) {
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            for (int j = 1; i + j <= s.length(); j++) {
                String num = Integer.toString(j);
                String abbr = s.substring(0, i) + num + s.substring(i + j);
                result.add(abbr);
                generateHelper(i + 1 + num.length(), abbr, result); // skip 1b
            }
        }
    }
}

Leetcode: 321. Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:
First find out the maximum number for each array, and then merge it into a global maximal one. 

Code (Java):

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] result = new int[k];
        int n1 = nums1.length;
        int n2 = nums2.length;
        
        // step 1: find the largest number from each array, and merge into one
        for (int i = Math.max(0, k - n2); i <= Math.min(n1, k); i++) {
            int[] list1 = findMax(nums1, i);
            int[] list2 = findMax(nums2, k - i);
            
            // then merge into one
            int[] curr = merge(list1, list2);
            
            if (greater(curr, 0, result, 0)) {
                result = curr;
            }
        }
        
        return result;
    }
    
    private int[] findMax(int[] nums, int k) {
        int[] result = new int[k];
        
        int n = nums.length;
        int len = 0;
        for (int i = 0; i < n; i++) {
            while (len > 0 && len + n - i > k && nums[i] > result[len - 1]) {
                len--;
            }
            
            if (len < k) {
                result[len] = nums[i];
                len++;
            }
        }
        
        return result;
    }
    
    private int[] merge(int[] list1, int[] list2) {
        int n1 = list1.length;
        int n2 = list2.length;
        
        int[] result = new int[n1 + n2];
        
        int i = 0; 
        int j = 0;
        int k = 0;
        
        while (k < n1 + n2) {
            if (greater(list1, i, list2, j)) {
                result[k++] = list1[i++];
            } else {
                result[k++] = list2[j++];
            }
        }
        
        return result;
    }
    
    private boolean greater(int[] list1, int pos1, int[] list2, int pos2) {
        int n1 = list1.length;
        int n2 = list2.length;
        
        while (pos1 < n1 && pos2 < n2 && list1[pos1] == list2[pos2]) {
            pos1++;
            pos2++;
        }
        
        if (pos2 == n2) {
            return true;
        }
        
        if (pos1 < n1 && list1[pos1] > list2[pos2]) {
            return true;
        }
        
        return false;
    }
}

Leetcode: 327. Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution 1: Use Segment Tree

Solution 2: Use Binary Search Tree

Leetcode: 325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution:
The idea of the problem is to check where there is a range from i to j, inclusive, so that its sum equals to k, and the length of the range is the maximum. 

So we can naturally think of this question as a range summary problem, and we need to calculate the prefix sum of the array first. So the sum(i, j) = presum[j] - presum[i - 1] = k

In order to achieve the O(n) time, we can leverage the same idea of the "Two Sum" problem by using a hash map. So we store the presum[i - 1] + k into the map, and check if presum[j] is in the map for each iteration. Note that we can do this in one-pass of loop iteration because for each j, i - 1 must be in the position above j. 

Code (Java):

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // step 1: calculate the prefix sum for all numbers of the nums array
        int n = nums.length;
        int[] preSum = new int[n + 1];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            preSum[i + 1] = sum;
        }
        
        // step 2: put the preSum + target into a map
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < preSum.length; j++) {
            if (map.containsKey(preSum[j])) {
                max = Math.max(max, j - map.get(preSum[j]));
            }
            
            if (!map.containsKey(preSum[j] + k)) {
                map.put(preSum[j] + k, j);
            }
        }
        
        
        return max;
    }
}