/leetcode

Repo. for leetcode algorithm problems

Primary LanguageC++

Subarry
Sum Prefix Sum
Min Mono Stack

Mono Stack

Prefix Sum

Subarray Target Sum

See Problem 560, very useful.

C++ Weapons

Function Method
Reverse a vector std::reverse
First element less than provided std::upper_bound
First element greater than provided std::lower_bound
Find string/characterin string std::string.find

Problem

370. Range Addition

Intuition

  • The value in the result only changes at range boundaries
  • The left boundary will contribute +inc
  • The right boundary will contribute -inc

Approach

  1. Scan the ranges and calculate the contribution
  2. Scan the array and calculate the running sum

Complexity

  • Time complexity: $O(M+N)$
  • Space complexity: $O(N)$

1310. XOR Queries of a Subarray

Simple prefix XOR;

1074. Number of Submatrices That Sum to Target

  • 2D prefix sum & subarray sum to target problem
  • Time complexity $O(M^2N)$

1788. Maximize the Beauty of the Garden

  • Negative flowers affect the total beauty
  • Iterate over valid pairs

2083. Substrings That Begin and End With the Same Letter

Intuition

Complexity

  • Time complexity: $O(n)$
  • Space complexity: $O(1)$

Code

class Solution {
public:
    long long numberOfSubstrings(string s) {
        int n = s.size();
        long long ret = 0;
        long long hash[26] = {0};
        
        for(int i = 0;i < n;++i){
            ret += hash[s[i] - 'a'];
            hash[s[i] - 'a']++;
        }

        return ret + n;
    }
};