Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
 

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

My solution

My solution is using the sliding window method. We use two pointers, left and right, to represent the left and right bound of the subarray. We move the right pointer to the right until the sum of the subarray is greater than or equal to the target. Then we move the left pointer to the right and update the minimun length of the subarray. We repeat the process until the right pointer reaches the end of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minCount = INT_MAX;
        int n = nums.size();
        while (right < n){
            sum += nums[right];
            right ++;
            while (sum >= target){
                minCount = min(right - left, minCount);
                sum -= nums[left];
                left ++;
            }
        }
        return (minCount == INT_MAX) ? 0 : minCount;
    }
};

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
 

Constraints:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Solution by Two Pointers

I didn’t complete this question by my own. The idea of solving this question is to sort the array from small to large first, then iterate each element in the array and use two pointers to find the other two elements.

One thing to mention is that we skip the same items during the iteration to avoid duplicate triplets.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort (nums.begin(), nums.end());
        vector<vector<int>> answer;
        int n = nums.size();
        for (int i = 0; i < n - 2; i++){
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1;
            int right = n - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0){
                    answer.push_back({nums[i], nums[left],nums[right]});
                    while (left < right && nums[left] == nums[left+1])
                        left ++;
                    while (left < right && nums[right] == nums[right - 1])
                        right --;
                    left ++;
                    right --;
                }
                else if (sum < 0) 
                    left ++;
                else
                    right --; 
            }
        }
        return answer;
    }
};

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Example 1:


Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:

Input: height = [1,1]
Output: 1
 

Constraints:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

My solution

My solution is using the two pointers method. As what we want is the maximum water we could have, we need to find the height and the width. The height is determined by the lower height of two lines, while the width is the distance between two lines. Therefore, we use two pointers to find the maximum water. The left pointer starts from the leftmost line and the right pointer starts from the rightmost line. We find the lower height between them, times the width between them. If the result is greater than the current maxWater, we replace it. If the left pointer is the shorter one, we move to the next height, whearas we move the right pointer to left. We repeat the process until the two pointers meet each other.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int maxWater = 0;
        int left = 0;
        int right = n - 1;
        while (left < right){
            int minHeight = min(height[left], height[right]);
            if (minHeight * (right - left)> maxWater)
                maxWater = minHeight * (right - left);
            if (height[left] > height[right])
                right --;
            else
                left ++;
        }
        return maxWater;
    }
};

Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
 

Constraints:

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.

My solution

My solution is initialise the first number as the variable first and the last number as the variable last. Then we add these two numbers, if they are larger than the target, we set the last number as the previous number of the last number. If they are smaller than the target, we set the first number as the next number of the first number. If they are equal to the target, we return the index of the first number and the last number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int j = n - 1;
        int i = 0;
        int first = numbers[i];
        int last = numbers[j];
        while (first + last != target){
            if (first + last > target){
                j --;
                last = numbers[j];
            }
            else{
                i++;
                first = numbers[i];
            }
        }
        vector <int> answer;
        answer.push_back(i+1);
        answer.push_back(j+1);
        return answer;
    }
};

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
 

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

My solution

My solution is convert all uppercase letters to lowercase, meanwhile, remove all non-alphanumeric characters by comparing the ASCII Value. Then, we use two pointers to check if the string is a palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool isPalindrome(string s) {
        string answer = "";
        // tolower() is a string to transform all uppercase letters to lowercase
        for (int i = 0; i < s.size(); i++){
            // ASCII Value of uppercase letters is from 65 to 90
            if (s[i] >= 65 && s[i] <= 90)
                answer += tolower(s[i]);
            // ASCII Value of lowercase letters is from 97 to 122 and the ASCII Value of numbers is from 48 to 57
            else if ( s[i] >= 97 && s[i] <= 122 || s[i] >= 48 && s[i] <= 57)
                answer += s[i];
        }
        int j = answer.size() - 1;
        for (int i = 0; i <= j ; i++){
            if (answer[i] != answer[j])
                return false;
            j --;
        }
        return true;
    }
};

Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
 

Constraints:

0 <= x <= 231 - 1

My solution

My solution is intuitive and simple, but it costs O(n) time complexity.

Once a number’s square is larger than x, we return the previous number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int mySqrt(int x) {
        long i = 0;
        while (true){
            long j = i + 1;
            if (i * i <= x && j * j > x)
                return i;
            else 
                i ++;
        }
        return -1;
    }
};

Binary Search

Then I saw a solution that using binary search to solve it. It costs O(logn) time complexity.
In this solution, we find the mid number between first (which is initiated as 1) and last (which is initiated as x). If the mid number is equal to x / mid, we return mid. If the mid number is larger than x / mid, we set last as mid - 1. If the mid number is smaller than x / mid, we set first as mid + 1.

Finally, if the first is larger than the last, we return last.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0)
            return 0;
        int first = 1, last = x;
        while (first <= last){
            int mid = (first+ (last - first)/2);
            if (mid == x / mid)
                return mid;
            else if (mid >= x / mid)
                last = mid - 1;
            else first = mid + 1;
        }
        return last;

    }
};

Text Justification

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note:

A word is defined as a character sequence consisting of non-space characters only.
Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Example 1:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Example 2:

Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.
Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]
 

Constraints:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth

Solution

I didn’t find the solution by my own, so this is a good solution from the community with my understanding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> result;
        // the index where the current line starts.
        int start = 0;

        while (start <words.size()) {
            // Helps to find the last word that can fit in the current line.
            int end = start;
            // The length of the current line if words were just joined without extra spaces
            int lineLength = words[end].length();

            // The inner while loop checks if the next word can fit on the current line.
            //If it fits, end is incremented, and the length of the next word is added to lineLength.
            // The condition (end + 1 - start) calculates the minimum number of spaces required (one space for each word except the last one).

            while (end + 1 < words.size() && lineLength + words[end + 1].length() + (end + 1 - start) <= maxWidth) {
                ++end;
                lineLength += words[end].length();
            }

            string line = words[start];
            int numWords = end - start;

            if (end == words.size() - 1 || numWords == 0) { // Left justify for last line or single word line
                for (int i = start + 1; i <= end; ++i) {
                    line += " " + words[i];
                }
                line += string(maxWidth - line.length(), ' ');
            } else {
                // If not the last line
                // Calculate total spaces that need to be added to this line.
                int totalSpaces = maxWidth - lineLength;
                // Determine the average spaces between each word
                int spacesBetweenWords = totalSpaces / numWords;
                // Calculate extra spaces that cannot be evenly divided among words
                int extraSpaces = totalSpaces % numWords;

                for (int i = start + 1; i <= end; ++i) {
                    // Determine the number of spaces before this word (spacesBetweenWords + 1 if there are extra spaces left, spacesBetweenWords otherwise).
                    int spaces = spacesBetweenWords + (extraSpaces-- > 0 ? 1 : 0);
                    line += string(spaces, ' ') + words[i];
                }
            }
            // After constructing the current line, push it to the result.
            // Move start to end + 1 for processing the next line.
            result.push_back(line);
            start = end + 1;
        }

        return result;
    }
};

Zigzag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I
Example 3:

Input: s = "A", numRows = 1
Output: "A"
 

Constraints:

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000

Solution

I asked chatGPT for help and it shows me the pseudo code and the idea:

Let’s first understand the pattern of the zigzag.

For numRows = 3, the sequence of rows for the characters is: 0, 1, 2, 1, 0, 1, 2, 1, 0...

For numRows = 4, the sequence is: 0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0...

So, the pattern is basically to increment the row number from 0 to numRows - 1, then decrement it back to 0, and repeat.

Given this understanding, you can approach this problem using the following steps:

1. Initialize an array of strings rows of size numRows.
2. Iterate through each character of the input string s.
3. For each character, determine its row in the zigzag pattern and append it to the corresponding row’s string in the rows array.
4. Finally, concatenate all the rows to get the final result.

Here’s the pseudocode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function convert(s, numRows):
    if numRows == 1:
        return s

    rows = array of empty strings of size numRows
    currentRow = 0
    direction = -1  // -1 for moving up, 1 for moving down

    for each character c in s:
        rows[currentRow] += c

        // Change direction if we're at the top or bottom
        if currentRow == 0 or currentRow == numRows - 1:
            direction *= -1

        currentRow += direction

    result = concatenate all strings in rows
    return result

Here’s the corresponding C++ code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

string convert(string s, int numRows) {
    if (numRows == 1) return s;
    
    vector<string> rows(min(numRows, int(s.size())));
    int currentRow = 0;
    int direction = -1;  // -1 for moving up, 1 for moving down

    for (char c : s) {
        rows[currentRow] += c;

        if (currentRow == 0 || currentRow == numRows - 1) {
            direction *= -1;
        }

        currentRow += direction;
    }

    string result;
    for (string row : rows) {
        result += row;
    }
    return result;
}

Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"
Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
 

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

My solution

My solution is very intuitive, firstly, I iterate the whole string, and store all the word into an array. Then we iterate the array from back to front, and combine the words with a space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    string reverseWords(string s) {
        string output = "";
        string word ="";
        
        vector <string> words;
        int n = s.size();
        for (int i = 0; i < n; i++){
            if (s[i] == ' ' && word.size() != 0){
                words.push_back(word);
                word = "";
                continue;
            }
            if (s[i] == ' ' && word.size() == 0)
                continue;
            word += s[i];
        }
        if (word != "")
            words.push_back(word);
        int words_size = words.size();
        for (int i = words_size-1; i >= 0; i--){

            output += words[i];
            if (i != 0) output += ' ';
        }
        return output;
    }
};

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
 

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

My solution

My idea is to compare the character of one word to the others which are in the same position. If all the characters on the same position are same, we add this character to our return string, then we go to the next position, once the characters are not the same, we return the string. Here is my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string commonPrefix = "";
        for (int i = 0; i < strs[0].size(); i++){
            char cache = strs[0][i];
            for (int j = 1; j < strs.size(); j++){
                if (strs[j][i] == cache)
                    cache = strs[j][i];
                else
                    return commonPrefix;
            }
            commonPrefix += cache;
        }
        return commonPrefix;
    }
};

Sort lexicographically solution

The main idea of this solution is that:

If the array is sorted alphabetically then you can assume that the first element of the array and the last element of the array will have most different prefixes of all comparisons that could be made between strings in the array. If this is true, you only have to compare these two strings.

And this is the step:

1. Initialize an empty string ans to store the common prefix.
2. Sort the input list v lexicographically. This step is necessary because the common prefix should be common to all the strings, so we need to find the common prefix of the first and last string in the sorted list.
3. Iterate through the characters of the first and last string in the sorted list, stopping at the length of the shorter string.
4. If the current character of the first string is not equal to the current character of the last string, return the common prefix found so far.
5. Otherwise, append the current character to the ans string.
6. Return the ans string containing the longest common prefix.

And this is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    string longestCommonPrefix(vector<string>& v) {
        string ans="";
        sort(v.begin(),v.end());
        int n=v.size();
        string first=v[0],last=v[n-1];
        for(int i=0;i<min(first.size(),last.size());i++){
            if(first[i]!=last[i]){
                return ans;
            }
            ans+=first[i];
        }
        return ans;
    }
};