Self Crossing – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
You are given an array of integers distance
.
You start at point (0,0)
on an X-Y plane and you move distance[0]
meters to the north, then distance[1]
meters to the west, distance[2]
meters to the south, distance[3]
meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.
Return true
if your path crosses itself, and false
if it does not.
Example 1:
Input: distance = [2,1,1,2] Output: true
Example 2:
Input: distance = [1,2,3,4] Output: false
Example 3:
Input: distance = [1,1,1,1] Output: true
Constraints:
1 <= distance.length <= 105
1 <= distance[i] <= 105
C++ Self Crossing LeetCode Solution
class Solution
{
public:
bool isSelfCrossing(vector<int>& x)
{
x.insert(x.begin(), 4, 0);
int len = x.size();
int i = 4;
// outer spiral
for (; i < len && x[i] > x[i - 2]; i++);
if (i == len) return false;
// check border
if (x[i] >= x[i - 2] - x[i - 4])
{
x[i - 1] -= x[i - 3];
}
// inner spiral
for (i++; i < len && x[i] < x[i - 2]; i++);
return i != len;
}
};
Java Self Crossing LeetCode Solution
public class Solution {
public boolean isSelfCrossing(int[] x) {
if (x.length <= 3) {
return false;
}
int i = 2;
// keep spiraling outward
while (i < x.length && x[i] > x[i - 2]) {
i++;
}
if (i >= x.length) {
return false;
}
// transition from spiraling outward to spiraling inward
if ((i >= 4 && x[i] >= x[i - 2] - x[i - 4]) ||
(i == 3 && x[i] == x[i - 2])) {
x[i - 1] -= x[i - 3];
}
i++;
// keep spiraling inward
while (i < x.length) {
if (x[i] >= x[i - 2]) {
return true;
}
i++;
}
return false;
}
}
Python 3 Self Crossing LeetCode Solution
def isSelfCrossing(self, x):
return any(d >= b > 0 and (a >= c or a >= c-e >= 0 and f >= d-b)
for a, b, c, d, e, f in ((x[i:i+6] + [0] * 6)[:6]
for i in xrange(len(x))))
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below