clueless coding // TODO: be smarter

LeetCode 650. 2 Keys Keyboard: Java Solution



Problem Statement


Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy: You can copy all the characters present on the notepad (partial copy is not allowed). Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Function Signature (Java):
  int minSteps(int n)

Inputs:
  3

Outputs:
  3

Intitally, we have a single 'A'.
In step 1, we copy:
  A
In step 2, we paste:
  AA
In step 3, we paste again:
  AAA



TL;DR Code Solution


public int minSteps(int n) {
    int[] dp = new int[n+1];

    for (int i = 2; i <= n; i++) {
        dp[i] = i;
        for (int j = i-1; j > 1; j--) {
            if (i % j == 0) {
                dp[i] = dp[j] + (i/j);
                break;
            }

        }
    }
    return dp[n];
}

LeetCode 3Sum: C++ Solution



TL;DR Code Solution


vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;

    for (int i = 0; i < (int)nums.size() - 2; i++) {
        int pin = nums[i];
        int left = i + 1;
        int right = (int)nums.size() - 1;
        while (left < right) {
            if (pin + nums[left] + nums[right] == 0) {
                int numLeft = nums[left];
                int numRight = nums[right];
                vector<int> current = {pin, nums[left], nums[right]};
                result.push_back(current);

                while (left < right && nums[left] == numLeft)
                    left++;

                while (left < right && nums[right] == numRight)
                    right--;
            }
            else if (pin + nums[left] + nums[right] < 0) {
                left++;
            }
            else {
                right--;
            }
        }

        while (i + 1 < nums.size() && nums[i + 1] == nums[i])
            i++;

    }

    return result;


}

LeetCode 259. 3 Sum Smaller: C++ Solution



Problem Statement


Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Function Signature (C++):
  int threeSumSmaller(vector<int>& nums, int target)

Inputs:
  nums = [-2, 0, 1, 3]
  target = 2

Outputs:
  2

Two triplets with sums less than 2 can be created:
  [-2, 0, 1]
  [-2, 0, 3]



TL;DR Code Solution


int threeSumSmaller(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());

    int count = 0;
    for (int i = 0; i < (int)nums.size() - 1; i++) {
        int pin = nums[i];
        int right = (int)nums.size() - 1;
        int left = i + 1;
        while (left < right) {
            int sum = pin + nums[left] + nums[right];
            if (sum < target) {
                count += right - left;
                left++;
            }
            else {
                right--;
            }
        }
    }
    return count;
}

LeetCode 18. 4Sum: CPP Solution



Problem Statement


Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Function Signature (C++):
  vector<vector<int>> fourSum(vector<int>& nums, int target)

Inputs:
  nums = [1, 0, -1, 0, -2, 2]
  target = 0

Outputs:
  [
    [-1,  0, 0, 1],
    [-2, -1, 1, 2],
    [-2,  0, 0, 2]
  ]



TL;DR Code Solution


vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());

    vector<vector<int>> result;

    int size = (int)nums.size();
    for (int i = 0; i < size - 3; i++) {
        int first = nums[i];
        for (int j = i + 1; j < size - 2; j++) {
            int second = nums[j];
            int left = j + 1;
            int right = size - 1;
            while (left < right) {
                int numLeft = nums[left];
                int numRight = nums[right];

                int sum = first + second + nums[left] + nums[right];
                if (sum == target) {
                    vector<int> current = {first, second, nums[left], nums[right]};
                    result.push_back(current);

                    while (left < right && nums[left] == numLeft)
                        left++;
                    while (left < right && nums[right] == numRight)
                        right--;
                }
                else if (sum < target) {
                    left++;
                }
                else {
                    right--;
                }
            }
            while (j + 1 < size  - 2 && nums[j+1] == nums[j])
                j++;
        }
            while (i + 1 < size  - 3 && nums[i+1] == nums[i])
                i++;
    }

    return result;
}

LeetCode 454. 4Sum II: C++ Solution



Problem Statement


Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Function Signature (C++):
  int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D)

Inputs:
  A = [ 1, 2]
  B = [-2,-1]
  C = [-1, 2]
  D = [ 0, 2]

Outputs:
  2

We can create two different tuples:
  (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0



TL;DR Code Solution


int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    unordered_map<int, int> sums;
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            sums[A[i] + B[j]]++;
        }
    }

    int count = 0;
    for (int i = 0; i < C.size(); i++) {
        for (int j = 0; j < D.size(); j++) {
            if (sums.find(-(C[i] + D[j])) != sums.end()) {
                count += sums[-(C[i] + D[j])];
            }
        }
    }

    return count;
}

LeetCode 454. 4Sum II: CPP Solution



Problem Statement


Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict.

If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Function Signature (C++):
  string addBoldTag(string s, vector<string>& dict)

Inputs:
  s = "abcxyz123"
  dict = ["abc","123"]

Outputs:
  "<b>abc</b>xyz<b>123</b>"

Inputs:
  s = "aaabbcc"
  dict = ["aaa","aab","bc"]

Outputs:
  "<b>aaabbc</b>c"



TL;DR Code Solution


string addBoldTag(string s, vector<string>& dict) {

    vector<bool> isBold(s.length());
    for (int i = 0; i < dict.size(); i++) {
        int searchIndex = s.find(dict[i], 0);
        while (s.find(dict[i], searchIndex) != std::string::npos) {
            for (int j = searchIndex; j < searchIndex + dict[i].length(); j++) {
                isBold[j] = true;
            }
            searchIndex = s.find(dict[i], searchIndex + 1);
        }        

    }

    int runner = 0;
    string result;
    while (runner < s.length()) {
        if (!isBold[runner]) {
            result += s[runner];
            runner++;
        }
        else {
            result += "<b>";
            while (runner < s.length() && isBold[runner]) {
                result += s[runner];
                runner++;
            }
            result += "</b>";
        }
    }

    return result;
}