3017. Count the Number of Houses at a Certain Distance II LeetCode Solution
In this guide, you will get 3017. Count the Number of Houses at a Certain Distance II LeetCode Solution with the best time and space complexity. The solution to Count the Number of Houses at a Certain Distance II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Houses at a Certain Distance II
You are given three positive integers n, x, and y.
In a city, there exist houses numbered 1 to n connected by n streets. There is a street connecting the house numbered i with the house numbered i + 1 for all 1 <= i <= n – 1 . An additional street connects the house numbered x with the house numbered y.
For each k, such that 1 <= k <= n, you need to find the number of pairs of houses (house1, house2) such that the minimum number of streets that need to be traveled to reach house2 from house1 is k.
Return a 1-indexed array result of length n where result[k] represents the total number of pairs of houses such that the minimum streets required to reach one house from the other is k.
Note that x and y can be equal.
Example 1:
Input: n = 3, x = 1, y = 3
Output: [6,0,0]
Explanation: Let’s look at each pair of houses:
– For the pair (1, 2), we can go from house 1 to house 2 directly.
– For the pair (2, 1), we can go from house 2 to house 1 directly.
– For the pair (1, 3), we can go from house 1 to house 3 directly.
– For the pair (3, 1), we can go from house 3 to house 1 directly.
– For the pair (2, 3), we can go from house 2 to house 3 directly.
– For the pair (3, 2), we can go from house 3 to house 2 directly.
Example 2:
Input: n = 5, x = 2, y = 4
Output: [10,8,2,0,0]
Explanation: For each distance k the pairs are:
– For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), and (5, 4).
– For k == 2, the pairs are (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), and (5, 3).
– For k == 3, the pairs are (1, 5), and (5, 1).
– For k == 4 and k == 5, there are no pairs.
Example 3:
Input: n = 4, x = 1, y = 1
Output: [6,4,2,0]
Explanation: For each distance k the pairs are:
– For k == 1, the pairs are (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), and (4, 3).
– For k == 2, the pairs are (1, 3), (3, 1), (2, 4), and (4, 2).
– For k == 3, the pairs are (1, 4), and (4, 1).
– For k == 4, there are no pairs.
Constraints:
2 <= n <= 105
1 <= x, y <= n
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3017. Count the Number of Houses at a Certain Distance II LeetCode Solution in C++
class Solution {
public:
// Same as 3015. Count the Number of Houses at a Certain Distance I
vector<long long> countOfPairs(int n, int x, int y) {
if (x > y)
swap(x, y);
const int ringLen = y - x + 1;
const int leftLineLen = x - 1;
const int rightLineLen = n - y;
vector<long long> ans(n);
ans = addVectors(ans, bothInRing(n, ringLen));
ans = addVectors(ans, bothInTheSameLine(n, leftLineLen));
ans = addVectors(ans, bothInTheSameLine(n, rightLineLen));
ans = addVectors(ans, lineToRing(n, leftLineLen, ringLen));
ans = addVectors(ans, lineToRing(n, rightLineLen, ringLen));
ans = addVectors(ans, lineToLine(n, x, y, leftLineLen, rightLineLen));
for (long long& freq : ans)
freq *= 2;
return ans;
}
private:
// Returns the contribution from the scenario where two houses are located in
// the ring.
vector<long long> bothInRing(int n, int ringLen) {
vector<long long> res(n);
for (int k = 1; k <= (ringLen - 1) / 2; ++k)
res[k - 1] += ringLen;
if (ringLen % 2 == 0)
res[ringLen / 2 - 1] += ringLen / 2;
return res;
}
// Returns the contribution from the scenario where two houses are either
// located in the left line [1, x) or the right line (y, n].
vector<long long> bothInTheSameLine(int n, int lineLen) {
vector<long long> res(n);
for (int k = 1; k <= lineLen; ++k)
res[k - 1] += lineLen - k;
return res;
}
// Returns the contribution from the scenario where one house is either
// located in the left line [1, x) or the right line (y, n] and the other
// house is located in the cycle.
vector<long long> lineToRing(int n, int lineLen, int ringLen) {
vector<long long> res(n);
for (int k = 1; k <= lineLen + ringLen; ++k) {
// min(
// at most k - 1 since we need to give 1 to the line,
// at most ringLen / 2 since for length > ringLen / 2, it can always be
// calculated as ringLen - ringLen / 2
// )
const int maxInRingLen = min(k - 1, ringLen / 2);
// max(at least 0, at lest k - lineLen)
const int minInRingLen = max(0, k - lineLen);
if (minInRingLen <= maxInRingLen) {
// Each ring length contributes 2 to the count due to the split of
// paths when entering the ring: One path traverses the upper half of
// the ring, and the other traverses the lower half.
// This is illustrated as follows:
// Path 1: ... -- x -- (upper half of the ring)
// Path 2: ... -- x -- (lower half of the ring)
res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2;
if (minInRingLen == 0)
// Subtract 1 since there's no split.
res[k - 1] -= 1;
if (maxInRingLen * 2 == ringLen)
// Subtract 1 since the following case only contribute one:
// ... -- x -- (upper half of the ring) -- middle point
// ... -- x -- (upper half of the ring) -- middle point
res[k - 1] -= 1;
}
}
return res;
}
// Returns the contribution from the scenario where one house is in the left
// line [1, x) and the other house is in the right line (y, n].
vector<long long> lineToLine(int n, int x, int y, int leftLineLen,
int rightLineLen) {
vector<long long> res(n);
for (int k = 1; k <= leftLineLen + rightLineLen + 2; ++k) {
// min(
// at most leftLineLen,
// at most k - 1 - (x < y) since we need to give 1 to the right line
// and if x < y we need to give another 1 to "x - y".
// )
const int maxInLeft = min(leftLineLen, k - 1 - (x < y));
// max(at least 1, at least k - rightLineLen - (x < y))
const int minInLeft = max(1, k - rightLineLen - (x < y));
if (minInLeft <= maxInLeft)
res[k - 1] += maxInLeft - minInLeft + 1;
}
return res;
}
vector<long long> addVectors(const vector<long long>& a,
const vector<long long>& b) {
vector<long long> res(a.size());
transform(a.begin(), a.end(), b.begin(), res.begin(), plus<int>());
return res;
};
}; /* code provided by PROGIEZ */
3017. Count the Number of Houses at a Certain Distance II LeetCode Solution in Java
class Solution {
// Same as 3015. Count the Number of Houses at a Certain Distance I
public long[] countOfPairs(int n, int x, int y) {
if (x > y) {
final int temp = x;
x = y;
y = temp;
}
final int ringLen = y - x + 1;
final int leftLineLen = x - 1;
final int rightLineLen = n - y;
long[] ans = new long[n];
ans = addVectors(ans, bothInRing(n, ringLen));
ans = addVectors(ans, bothInTheSameLine(n, leftLineLen));
ans = addVectors(ans, bothInTheSameLine(n, rightLineLen));
ans = addVectors(ans, lineToRing(n, leftLineLen, ringLen));
ans = addVectors(ans, lineToRing(n, rightLineLen, ringLen));
ans = addVectors(ans, lineToLine(n, x, y, leftLineLen, rightLineLen));
for (int i = 0; i < ans.length; ++i)
ans[i] *= 2;
return ans;
}
// Returns the contribution from the scenario where two houses are located in
// the ring.
private long[] bothInRing(int n, int ringLen) {
long[] res = new long[n];
for (int k = 1; k <= (ringLen - 1) / 2; ++k)
res[k - 1] += ringLen;
if (ringLen % 2 == 0)
res[ringLen / 2 - 1] += ringLen / 2;
return res;
}
// Returns the contribution from the scenario where two houses are either
// located in the left line [1, x) or the right line (y, n].
private long[] bothInTheSameLine(int n, int lineLen) {
long[] res = new long[n];
for (int k = 1; k <= lineLen; ++k)
res[k - 1] += lineLen - k;
return res;
}
// Returns the contribution from the scenario where one house is either
// located in the left line [1, x) or the right line (y, n] and the other
// house is located in the cycle.
private long[] lineToRing(int n, int lineLen, int ringLen) {
long[] res = new long[n];
for (int k = 1; k <= lineLen + ringLen; ++k) {
// min(
// at most k - 1 since we need to give 1 to the line,
// at most ringLen / 2 since for length > ringLen / 2, it can always be
// calculated as ringLen - ringLen / 2
// )
final int maxInRingLen = Math.min(k - 1, ringLen / 2);
// max(at least 0, at lest k - lineLen)
final int minInRingLen = Math.max(0, k - lineLen);
if (minInRingLen <= maxInRingLen) {
// Each ring length contributes 2 to the count due to the split of
// paths when entering the ring: One path traverses the upper half of
// the ring, and the other traverses the lower half.
// This is illustrated as follows:
// Path 1: ... -- x -- (upper half of the ring)
// Path 2: ... -- x -- (lower half of the ring)
res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2;
if (minInRingLen == 0)
// Subtract 1 since there's no split.
res[k - 1] -= 1;
if (maxInRingLen * 2 == ringLen)
// Subtract 1 since the following case only contribute one:
// ... -- x -- (upper half of the ring) -- middle point
// ... -- x -- (upper half of the ring) -- middle point
res[k - 1] -= 1;
}
}
return res;
}
// Returns the contribution from the scenario where one house is in the left
// line [1, x) and the other house is in the right line (y, n].
private long[] lineToLine(int n, int x, int y, int leftLineLen, int rightLineLen) {
long[] res = new long[n];
for (int k = 1; k <= leftLineLen + rightLineLen + 2; ++k) {
// min(
// at most leftLineLen,
// at most k - 1 - (x < y) since we need to give 1 to the right line
// and if x < y we need to give another 1 to "x - y".
// )
final int maxInLeft = Math.min(leftLineLen, k - 1 - (x < y ? 1 : 0));
// max(at least 1, at least k - rightLineLen - (x < y))
final int minInLeft = Math.max(1, k - rightLineLen - (x < y ? 1 : 0));
if (minInLeft <= maxInLeft)
res[k - 1] += maxInLeft - minInLeft + 1;
}
return res;
}
private long[] addVectors(long[] a, long[] b) {
for (int i = 0; i < a.length; ++i)
a[i] += b[i];
return a;
}
} // code provided by PROGIEZ
3017. Count the Number of Houses at a Certain Distance II LeetCode Solution in Python
class Solution:
# Same as 3015. Count the Number of Houses at a Certain Distance I
def countOfPairs(self, n: int, x: int, y: int) -> list[int]:
if x > y:
x, y = y, x
def bothInRing(ringLen: int) -> list[int]:
"""
Returns the contribution from the scenario where two houses are located
in the ring.
"""
res = [0] * n
for k in range(1, (ringLen - 1) // 2 + 1):
res[k - 1] += ringLen
if ringLen % 2 == 0:
res[ringLen // 2 - 1] += ringLen // 2
return res
def bothInTheSameLine(lineLen: int) -> list[int]:
"""
Returns the contribution from the scenario where two houses are either
located in the left line [1, x) or the right line (y, n].
"""
res = [0] * n
for k in range(1, lineLen + 1):
res[k - 1] += lineLen - k
return res
def lineToRing(lineLen: int, ringLen: int) -> list[int]:
"""
Returns the contribution from the scenario where one house is either
located in the left line [1, x) or the right line (y, n] and the
other house is located in the cycle.
"""
res = [0] * n
for k in range(1, lineLen + ringLen):
# min(
# at most k - 1 since we need to give 1 to the line,
# at most ringLen / 2 since for length > ringLen / 2, it can always be
# calculated as ringLen - ringLen / 2
# )
maxInRingLen = min(k - 1, ringLen // 2)
# max(at least 0, at lest k - lineLen)
minInRingLen = max(0, k - lineLen)
if minInRingLen <= maxInRingLen:
# Each ring length contributes 2 to the count due to the split of
# paths when entering the ring: One path traverses the upper half of
# the ring, and the other traverses the lower half.
# This is illustrated as follows:
# Path 1: ... -- x -- (upper half of the ring)
# Path 2: ... -- x -- (lower half of the ring)
res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2
if minInRingLen == 0:
# Subtract 1 since there's no split.
res[k - 1] -= 1
if maxInRingLen * 2 == ringLen:
# Subtract 1 since the following case only contribute one:
# ... -- x -- (upper half of the ring) -- middle point
# ... -- x -- (upper half of the ring) -- middle point
res[k - 1] -= 1
return res
def lineToLine(leftLineLen: int, rightLineLen: int) -> list[int]:
"""
Returns the contribution from the scenario where one house is in the left
line [1, x) and the other house is in the right line (y, n].
"""
res = [0] * n
for k in range(leftLineLen + rightLineLen + 2):
# min(
# at most leftLineLen,
# at most k - 1 - (x < y) since we need to give 1 to the right line
# and if x < y we need to give another 1 to "x - y".
# )
maxInLeft = min(leftLineLen, k - 1 - (x < y))
# max(at least 1, at least k - rightLineLen - (x < y))
minInLeft = max(1, k - rightLineLen - (x < y))
if minInLeft <= maxInLeft:
res[k - 1] += maxInLeft - minInLeft + 1
return res
ringLen = y - x + 1
leftLineLen = x - 1
rightLineLen = (n - y)
ans = [0] * n
ans = list(map(operator.add, ans, bothInRing(ringLen)))
ans = list(map(operator.add, ans, bothInTheSameLine(leftLineLen)))
ans = list(map(operator.add, ans, bothInTheSameLine(rightLineLen)))
ans = list(map(operator.add, ans, lineToRing(leftLineLen, ringLen)))
ans = list(map(operator.add, ans, lineToRing(rightLineLen, ringLen)))
ans = list(map(operator.add, ans, lineToLine(leftLineLen, rightLineLen)))
return [freq * 2 for freq in ans] # code by PROGIEZ
