LeetCode : BruteForce vs Optimized

4MB

DSA 75.pdf

pdf

Must try this in last moment with Brute force and Optimized Apporach

1512. Number of Good Pair

BruteForce

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] == nums[j])
                    count++;
            }
        }

        return count;
    }
};

Optimal using Map

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> counter;
        int count = 0;

        for (int i = 0; i < nums.size(); i++) {
            count += counter[nums[i]]++;
        }

        return count;
    }
};

118. Pascal's Triangle

Using 2d Vector

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> pascale(numRows);

        for (int i = 0; i < numRows; i++) {
            pascale[i].resize(i + 1);
            pascale[i][0] = pascale[i][i] = 1;

            for (int j = 1; j < i; j++) {
                pascale[i][j] = pascale[i - 1][j - 1] + pascale[i - 1][j];
            }
        }

        return pascale;
    }
};

53. Maximum Subarray

Dp

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        int ans = dp[0];

        for (int i = 1; i < n; i++) {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            ans = max(ans, dp[i]);
        }

        return ans;
    }
};