/
ArithmeticSlices.java
163 lines (108 loc) · 3.76 KB
/
ArithmeticSlices.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/*
Source: https://leetcode.com/problems/arithmetic-slices/
Total 5 Approaches
1st approach (brute force)
Time: O(n ^ 2), where n is the length of the given array(nums)
Space: O(1), in-place
*/
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;
int arithmeticSubArrays = 0;
for(int i = 0; i < len - 2; ++i) {
int diff = nums[i] - nums[i + 1];
int count = 1;
for(int j = i + 1; j < len - 1 && (nums[j] - nums[j + 1]) == diff; ++j) {
if(++count >= 2) {
++arithmeticSubArrays;
}
}
}
return arithmeticSubArrays;
}
}
--------------------------------------------------------------------------------------------------------------------------------
/*
Approach 2 (brute force, but without using extra count variable)
Time: O(n ^ 2), where n is the length of the given array(nums)
Space: O(1), in-place
*/
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;
int arithmeticSubArrays = 0;
for(int i = 0; i < len - 2; ++i) {
int diff = nums[i + 1] - nums[i];
for(int j = i + 2; j < len && nums[j] - nums[j - 1] == diff; ++j) {
++arithmeticSubArrays;
}
}
return arithmeticSubArrays;
}
}
--------------------------------------------------------------------------------------------------------------------------------
/*
Approach 3 (more optimised, but uses extra space)
Time: O(n), where n is the length of the given array(nums)
Space: O(n), an array of size equal to the length of given array(nums) is required
*/
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;
int arithmeticSubArrays = 0;
int[] dp = new int[len];
for(int i = 2; i < len; ++i) {
if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
dp[i] = dp[i - 1] + 1;
arithmeticSubArrays += dp[i];
}
}
return arithmeticSubArrays;
}
}
--------------------------------------------------------------------------------------------------------------------------------
/*
Approach 4 (more optimised than Approach 3 by eliminating extra array for space)
1. Minimum 3 indices are required to make arithmetic progression
2. Starting with index 2, if we found 2 same differences i.e. if the diff of 2 consecutive elements is same as diff of previous 2 consecutive elements,
it means that we have got the arithmetic sequence and the running sequence gets extended upto ith index, so increment the curr by 1 and add this curr to arithmeticSubArrays
3. If we found that ith index doesn't form arithmetic sequence, then make currently running sequence to 0(zero)
Time: O(n), where n is the length of the given array(nums)
Space: O(1), in-place
*/
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int curr = 0;
int len = nums.length;
int arithmeticSubArrays = 0;
for(int i = 2; i < len; ++i) {
if(nums[i - 1] - nums[i - 2] == nums[i] - nums[i - 1]) {
arithmeticSubArrays += ++curr;
} else {
curr = 0;
}
}
return arithmeticSubArrays;
}
}
--------------------------------------------------------------------------------------------------------------------------------
/*
Approach 5 (eliminating if/else condition)
Time: O(n), where n is the length of the given array(nums)
Space: O(1), in-place
*/
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int len = nums.length;
int arithmeticSubArrays = 0;
for(int i = 2; i < len; ++i) {
int diff = nums[i - 1] - nums[i - 2];
int curr = 0;
while(i < len && nums[i] - nums[i - 1] == diff) {
arithmeticSubArrays += ++curr;
++i;
}
}
return arithmeticSubArrays;
}
}