Arithmetic Subarrays | 2 Approaches | Sorting | Without Sorting | Leetcode-1630

Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 71st Video on ourArray Playlist
In this video we will try to solve a very good problem - Arithmetic Subarrays (Leetcode -1630).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Arithmetic Subarrays
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/arithme...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[@kunjalsingh321]

this question was asked in atlassian oa test for females

[@codestorywithMIK]

Thank you so much for sharing. I will update it in my Github 🙏🙏

[@oqant0424]

ur Consistency 🔥🔥🔥🔥

[@anuppatankar4294]

Great Video👌🏻

[@aadil4236]

I really like these kind of array problem. The first data structure I ever learned.

[@oqant0424]

Thanks bhaiya 🙌

[@sauravchandra10]

The second approach was as always amazing!

[@DeveloperRB]

I configured the logic on my own then for confirmation I always come here and at 3:30 got Confirmed..
So 🥰 solved the question,
now watching for approach 2 and intuitions
Love your work MIK 💖

[@ugcwithaddi]

Nice 👌🏻

[@dayashankarlakhotia4943]

Good explanation 🎉❤

[@tutuimam3381]

Thanks ❤❤

[@user-ow1vq7uv7e]

love u bhaiya ❤️❤️… keep creating such contains 💕

[@de_coder1]

I was able to code approach 1 myself, approach 2 was new for me

[@shabananoor9423]

Amazing 😅😅

[@YourCodeVerse]

1588. Sum of All Odd Length Subarrays
Please cover this problem also

[@codeandtalk6]

❤❤❤

[@madugulajoshi5050]

Hey i have a doubt in my approach.
For checking if its in arithmetic progression or not.
I first computed the sum of the elements for the given range and also the min and max element.
Then found the common difference d.
Then i found the sum of ap using the formula.
And tried to check if these both suma are equal or not then we can say if its in ap.
It passed for many test cases. But failed for few.
I dont understand whats wrong with my approach.
Can you please tell

[@kokkiligovinda1943]

Python Solution:
method 1 : using sorting
class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
ans = []
def is_arithmetic_sequence(arr) :
arr.sort()
d = arr[1] - arr[0]
for i in range(2,len(arr)):
if arr[i] - arr[i-1] != d :
return False
return True

for i, j in zip(l,r) :
ans.append(is_arithmetic_sequence(nums[i:j+1]))
return ans
method II : without using sorting
class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
ans = []
def is_arithmetic_sequence(arr) :
n = len(arr)
arr_set = set(arr)
min_ele = min(arr)
max_ele = max(arr)
d = (max_ele - min_ele)/(n-1)
cur_ele = min_ele
while cur_ele < max_ele:
cur_ele = cur_ele + d
if cur_ele not in arr_set :
return False
return True

for i, j in zip(l,r) :
ans.append(is_arithmetic_sequence(nums[i:j+1]))
return ans

[@piyushjaiswal9192]

In Approach 1 : Space complexity will be (m*n). m=number of queries and n =size of array in worst case full input array.

[@codestorywithMIK]

Thanks a lot for your input on this ❤️🙏

[@adwaitmhatre7561]

I think it will be O(n) only. We are not storing all m*n elements at one go. We are reusing the same array to fill elements as per the range which in worst case will be of length n

[@piyushjaiswal9192]

@@adwaitmhatre7561 take a case where all M queries have left to right range as N.
So for M queries
N + N +....+ Mtimes = total= M*N space complexity. Please correct me if i am wrong.

[@adwaitmhatre7561]

@@piyushjaiswal9192yes agreed but those M*N won’t be stored all together. They will be stored one by one (each range of length N at a time) as the for loop goes on. So in isolation, in every iteration of for loop we will be only using N space as the vector is reinitialised in every iteration

[@infinitygaming7192]

class Solution:
def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
arr = []
def check_if_ap(arr):
if len(arr) < 2:
return False
diff = arr[1] - arr[0]
for i in range(1,len(arr)):
if arr[i] - arr[i-1] != diff:
return False
return True
for i in range(len(l)):
sort_arr = sorted(nums[l[i]:r[i]+1])
arr.append(check_if_ap(sort_arr))
return arr

[@vrajpatel0218]

your code is time taken, i can apply your second approch my leet code show me 440 ms time complexity .

[@tapansonak1431]

whats your leetcode username bro