2025-09-02 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 2

Description

Find the Number of Ways to Place People I

You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi].

Count the number of pairs of points (A, B), where

  • A is on the upper left side of B, and
  • there are no other points in the rectangle (or line) they make (including the border).

Return the count.

 

Example 1:

Input: points = [[1,1],[2,2],[3,3]]

Output: 0

Explanation:

There is no way to choose A and B so A is on the upper left side of B.

Example 2:

Input: points = [[6,2],[4,4],[2,6]]

Output: 2

Explanation:

  • The left one is the pair (points[1], points[0]), where points[1] is on the upper left side of points[0] and the rectangle is empty.
  • The middle one is the pair (points[2], points[1]), same as the left one it is a valid pair.
  • The right one is the pair (points[2], points[0]), where points[2] is on the upper left side of points[0], but points[1] is inside the rectangle so it's not a valid pair.

Example 3:

Input: points = [[3,1],[1,3],[1,1]]

Output: 2

Explanation:

  • The left one is the pair (points[2], points[0]), where points[2] is on the upper left side of points[0] and there are no other points on the line they form. Note that it is a valid state when the two points form a line.
  • The middle one is the pair (points[1], points[2]), it is a valid pair same as the left one.
  • The right one is the pair (points[1], points[0]), it is not a valid pair as points[2] is on the border of the rectangle.

 

Constraints:

  • 2 <= n <= 50
  • points[i].length == 2
  • 0 <= points[i][0], points[i][1] <= 50
  • All points[i] are distinct.

Solution

class Solution {
public:
  int numberOfPairs(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b) {
      return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });
    int len = points.size();
    int answer = 0;
    for(int i = 0; i < len - 1; ++i) {
      int y = INT_MAX;
      for(int j = i + 1; j < len; ++j) {
        if(points[j][1] >= points[i][1] && y > points[j][1]) {
          answer += 1;
          y = points[j][1];
        }
      }
    }
    return answer;
  }
};

// Accepted
// 955/955 cases passed (4 ms)
// Your runtime beats 72.46 % of cpp submissions
// Your memory usage beats 97.83 % of cpp submissions (32.4 MB)
Algorithm