There are N points (numbered from 0 to N−1) on a plane. Each point is colored either red ('R') or green ('G'). The K-th point is located at coordinates (X[K], Y[K]) and its color is colors[K]. No point lies on coordinates (0, 0).
We want to draw a circle centered on coordinates (0, 0), such that the number of red points and green points inside the circle is equal. What is the maximum number of points that can lie inside such a circle? Note that it is always possible to draw a circle with no points inside.
Write a function:
class Solution { public int solution(int[] X, int[] Y, String colors); }
that, given two arrays of integers X, Y and a string colors, returns an integer specifying the maximum number of points inside a circle containing an equal number of red points and green points.
Examples:
1. Given X = [4, 0, 2, −2], Y = [4, 1, 2, −3] and colors = "RGRR", your function should return 2. The circle contains points (0, 1) and (2, 2), but not points (−2, −3) and (4, 4).
2. Given X = [1, 1, −1, −1], Y = [1, −1, 1, −1] and colors = "RGRG", your function should return 4. All points lie inside the circle.
3. Given X = [1, 0, 0], Y = [0, 1, −1] and colors = "GGR", your function should return 0. Any circle that contains more than zero points has an unequal number of green and red points.
4. Given X = [5, −5, 5], Y = [1, −1, −3] and colors = "GRG", your function should return 2.
5. Given X = [3000, −3000, 4100, −4100, −3000], Y = [5000, −5000, 4100, −4100, 5000] and colors = "RRGRG", your function should return 2.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of arrays X and Y is an integer within the range [−20,000..20,000];
- string colors is made only of the characters 'R' and/or 'G';
- no point lies on the coordinates (0, 0).
class Solution {
//B
class Point {
int r;
boolean isRed;
Point(int r, boolean isRed) {
this.r = r;
this.isRed = isRed;
}
}
public int solution(int[] X, int[] Y, String colors) {
int n = X.length;
int ans = 0;
ArrayList<Point> tab = new ArrayList<>();
for (int i = 0; i < n; i++) {
int r2 = X[i] * X[i] + Y[i] * Y[i];
tab.add(new Point(r2, colors.charAt(i) == 'R'));
}
tab.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.r - o2.r;
}
});
int cnt = 0;
int red = 0;
for (int i = 0; i < n; i++) {
// r2 = tab[i][0]
cnt++;
if (tab.get(i).isRed)
red++;
if (red * 2 == cnt && (i == n - 1 || tab.get(i).r != tab.get(i + 1).r))
ans = Math.max(ans, cnt);
}
return ans;
}
}
Solution.java:16: error: cannot find symbol
ArrayList<Point> tab = new ArrayList<>();
^
symbol: class ArrayList
location: class Solution
Solution.java:16: error: cannot find symbol
ArrayList<Point> tab = new ArrayList<>();
^
symbol: class ArrayList
location: class Solution
Solution.java:22: error: cannot find symbol
tab.sort(new Comparator<Point>() {
^
symbol: class Comparator
location: class Solution
Solution.java:24: error: method does not override or implement a method from a supertype
@Override
^
Solution.java:37: error: illegal parenthesized expression
if (tab.get(i).isRed)
^
5 errors
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
//B
class Point {
int r;
boolean isRed;
Point(int r, boolean isRed) {
this.r = r;
this.isRed = isRed;
}
}
public int solution(int[] X, int[] Y, String colors) {
int n = X.length;
int ans = 0;
ArrayList<Point> tab = new ArrayList<>();
for (int i = 0; i < n; i++) {
int r2 = X[i] * X[i] + Y[i] * Y[i];
tab.add(new Point(r2, colors.charAt(i) == 'R'));
}
tab.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.r - o2.r;
}
});
int cnt = 0;
int red = 0;
for (int i = 0; i < n; i++) {
// r2 = tab[i][0]
cnt++;
if (tab.get(i).isRed)
red++;
if (red * 2 == cnt && (i == n - 1 || tab.get(i).r != tab.get(i + 1).r))
ans = Math.max(ans, cnt);
}
return ans;
}
}
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
//B
class Point {
int r;
boolean isRed;
Point(int r, boolean isRed) {
this.r = r;
this.isRed = isRed;
}
}
public int solution(int[] X, int[] Y, String colors) {
int n = X.length;
int ans = 0;
ArrayList<Point> tab = new ArrayList<>();
for (int i = 0; i < n; i++) {
int r2 = X[i] * X[i] + Y[i] * Y[i];
tab.add(new Point(r2, colors.charAt(i) == 'R'));
}
tab.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.r - o2.r;
}
});
int cnt = 0;
int red = 0;
for (int i = 0; i < n; i++) {
// r2 = tab[i][0]
cnt++;
if (tab.get(i).isRed)
red++;
if (red * 2 == cnt && (i == n - 1 || tab.get(i).r != tab.get(i + 1).r))
ans = Math.max(ans, cnt);
}
return ans;
}
}
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
//B
class Point {
int r;
boolean isRed;
Point(int r, boolean isRed) {
this.r = r;
this.isRed = isRed;
}
}
public int solution(int[] X, int[] Y, String colors) {
int n = X.length;
int ans = 0;
ArrayList<Point> tab = new ArrayList<>();
for (int i = 0; i < n; i++) {
int r2 = X[i] * X[i] + Y[i] * Y[i];
tab.add(new Point(r2, colors.charAt(i) == 'R'));
}
tab.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.r - o2.r;
}
});
int cnt = 0;
int red = 0;
for (int i = 0; i < n; i++) {
// r2 = tab[i][0]
cnt++;
if (tab.get(i).isRed)
red++;
if (red * 2 == cnt && (i == n - 1 || tab.get(i).r != tab.get(i + 1).r))
ans = Math.max(ans, cnt);
}
return ans;
}
}
The solution obtained perfect score.
Small tests where all points have distinct distances from the origin. N <= 50.
Small tests where the proportion of color occurences is imbalanced. N <= 50.
Small tests where points are given in increasing order of distance from (0, 0). N <= 50.