611. Valid Triangle Number

Description:

https://leetcode.com/problems/valid-triangle-number/description/

Algorithm1:

Use for loop for three times.

It works but slow (beats 23.60%)

Code1:

class Solution {
public:
    int triangleNumber(vector&amp; nums) {
        if (nums.size() &lt; 3) return 0;
        int result = 0;
        sort(nums.begin(), nums.end());
        int threshold;
        for (int i = 0; i &lt; nums.size() - 2; i++)
        {
            for (int j = i + 1; j &lt; nums.size() - 1; j++)
            {
                threshold = nums[i] + nums[j];
                for (int k = j + 1; k &lt; nums.size(); k++)
                {
                    if (nums[k] &lt; threshold)
                        result++;
                    else
                        break;
                }
            }
        }
        return result;
    }
};

class Solution {

public:

int triangleNumber(vector& nums) {

if (nums.size() < 3) return 0;

int result = 0;

sort(nums.begin(), nums.end());

int threshold;

for (int i = 0; i < nums.size() - 2; i++)

{

for (int j = i + 1; j < nums.size() - 1; j++)

{

threshold = nums[i] + nums[j];

for (int k = j + 1; k < nums.size(); k++)

{

if (nums[k] < threshold)

result++;

else

break;

}

return result;

}

};

Timing & Space:

O(n^3) & O(1)

Algorithm2:

Code2:

class Solution {
public:
	int triangleNumber(vector&amp; nums) {
		long n = nums.size();
		int i, j, k;
		int total, a, b, c;
		if (n &lt; 3) return 0;
		vector ct(1001, 0), sum(2001, 0);
		vector&lt;pair&lt;long, long&gt;&gt; p;
		for (i = 0; i &lt; n; i++) 
			ct[nums[i]]++;
		
		sum[0] = 0;	// 0 cannot form triangle
		for (i = 1; i &lt;= 1000; i++) 
			sum[i] = sum[i - 1] + ct[i];
		
		p.clear();
		for (i = 1; i &lt;= 1000; i++) if (ct[i] &gt; 0) 
				p.push_back(make_pair(i, ct[i]));
		
		for (i = 1001; i &lt;= 2000; i++) sum[i] = sum[1000];
		c = p.size();

		total = 0;
		for (a = 0; a &lt; c; a++) { if (p[a].second &gt;= 2) {
				// a = b &lt; c; total += (sum[p[a].first * 2 - 1] - sum[p[a].first]) * (p[a].second * (p[a].second - 1) / 2); // a = b = c if (p[a].second &gt; 2)
					total += (p[a].second * (p[a].second - 1) / 2 * (p[a].second - 2) / 3);
			}
			for (b = a + 1; b &lt; c; b++) {
				// a &lt; b &lt; c
				total += (sum[p[a].first + p[b].first - 1] - sum[p[b].first]) * p[a].second * p[b].second;
				// a &lt; b = c if (p[b].second &gt; 1)
					total += p[a].second * (p[b].second * (p[b].second - 1) / 2);
			}
		}
		return total;
	}
};

class Solution {

public:

int triangleNumber(vector& nums) {

long n = nums.size();

int i, j, k;

int total, a, b, c;

if (n < 3) return 0;

vector ct(1001, 0), sum(2001, 0);

vector<pair<long, long>> p;

for (i = 0; i < n; i++)

ct[nums[i]]++;

sum[0] = 0; // 0 cannot form triangle

for (i = 1; i <= 1000; i++)

sum[i] = sum[i - 1] + ct[i];

p.clear();

for (i = 1; i <= 1000; i++) if (ct[i] > 0)

p.push_back(make_pair(i, ct[i]));

for (i = 1001; i <= 2000; i++) sum[i] = sum[1000];

c = p.size();

total = 0;

for (a = 0; a < c; a++) { if (p[a].second >= 2) {

// a = b < c; total += (sum[p[a].first * 2 - 1] - sum[p[a].first]) * (p[a].second * (p[a].second - 1) / 2); // a = b = c if (p[a].second > 2)

total += (p[a].second * (p[a].second - 1) / 2 * (p[a].second - 2) / 3);

}

for (b = a + 1; b < c; b++) {

// a < b < c

total += (sum[p[a].first + p[b].first - 1] - sum[p[b].first]) * p[a].second * p[b].second;

// a < b = c if (p[b].second > 1)

total += p[a].second * (p[b].second * (p[b].second - 1) / 2);

}

return total;

}

};

Timing & Space:

Time:

Worst: O(n^2)

Best: O(1)

Space: O(1)

Leave a Reply Cancel reply