![[FCO]FreeCoursesOnline](https://onehack.us/uploads/default/original/3X/b/4/b4d2fc8468becec1e9976784dba394e5a378ec81.jpg){kind=small}
Good morning folks, here is our Problem 3
Topics: Arrays/2-d arrays
This is a pretty standard problem in many coding interviews and may be easy for few of you guys but as i am just learning and most of us are on same boat so lets just put this out too.
Given a 2-D array you will have to print it out in the spiral clockwise order:
For example:
Best of luck 
Problem 3
testcase 1
if n is 3 , X is 1
and elements are {5,7,6}
the output must be {5,6}
can you tell me the correctness of you’re solution?
Is there any constraints?
Yep, It fails for down sums!
No , you may fill out aray values as you like. Here the question is to check implementation techniques.
the solution would be O(N) , not able to see any other soln atm.
Well it should be , because the question is to print all elements of the array.
Problem #4
Space Complexity O(MxN) + overhead
Time Complexity O(N) , all MxN elements are visited
Pseudocode
the pattern of spiral clockwise is formed till M/2 rows
(initially rowStart and colStart are 0,0)
the pattern as follows increase in currCol , once it reaches ColMax ,
increase currRow to RowMax (by increment +1)
now decrease col to ColStart (decrement by 1)
and now decrement row to RowStart (decrement by 1)
edge case once you reach back currRow and currCol to rowStart and colStart respectively
don’t print the element value { you can also remove this edge case by varying condition}
btw RowMax and ColMax are obtained from M-rowStart,N-colStart
the starting element is choosen from the position rowStart+1,ColStart +1 , rowStart,ColStart respectively.
Hi Guys i will post the my version of a detailed approach to solve problem 3 soon.
However here is today’s problem 4
Given an unsorted array you will have to print out the largest & the smallest number in the array. Topics: Arrays,Dynamic memory allocation, vectors
// You cannot sort the array here.
Inputs:
Output
print out max & minimum integer value present in array.
Example:
Inputs
5
6 4 10 1 60
Output
Max=60
Min=1
for problem #5
time complexity O(N)
problem # 6
Time complexity O(N) preferred
problem complexity medium
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.
For example, the length of your array of zeros n=10. Your list of queries is as follows:
a b k
1 5 3
4 8 7
6 9 1
Add the values of k between the indices a and b inclusive:
index-> 1 2 3 4 5 6 7 8 9 10
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]
The largest value is 10 after all operations are performed.
Function Description
create the function arrayManipulation It must return an integer, the maximum value in the resulting array.
arrayManipulation has the following parameters:
long arrayManipulation(int n, int[][] queries){
//code here*
}
Input Format
The first line contains two space-separated integers n and m , the size of the array and the number of operations.
Each of the next lines contains three space-separated integers a , b and k , the left index, right index and summed.
Constraints
3 <= n <= 10^71 <= m <= 10^71 <= a <= b <= n0 <= k <= 10^9Output Format
Return the integer maximum value in the finished array.
Sample Input
5 3
1 2 100
2 5 100
3 4 100
Sample Output
200
Explanation
After the first update list will be 100 100 0 0 0 .
After the second update list will be 100 200 100 100 100 .
After the third update list will be 100 200 200 200 100 .
The required answer will be 200
hint 1:
try to solve in O(N^2).
Didnt understood the question 
will give hints PM me with problem number , we can proceed with problem # 7
problem # 7 (variation of closest)
Given an array nums of n integers and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Can you please share the solution/logic ?
A naive approach would be O(n^3) , assuming you couldnt come up with naive approach.
better solution would be O(N^2) even better is O(NlogN).
Naive Approach
Have a map (prefer sorted tree) to contain all the min found with abs(target-3sum) , with 3sum
for i = 1 to n
for j = i+1 to n
for k = j+1 to n
3sum + nums[i]+nums[j]+nums[k]
find min add to map
end for k
end for j
end for i
return 3sum from tree found in the least value.
(btw this is one of the approach for naive)
Problem 8 Topics: Arrays/String
Given a string print out the sub-string of the given string.
Example:
Input: abcd
output:
a
ab
abc
abcd
b
bc
bcd
c
cd
d
primarily can think of 2 ways to solve the above combination problem.
using for loop and recursion.
prefer loop as i’m not sure you’re language supports tail call optimization
for i → 0 to len(str)
comb = ithStr
print(comb)
for j → i+1 to len(str)
comb = comb + jthStr
print(comb)
end forj
end fori
Note
comb = comb + jthStr
in some language + can be used for combining string. Some don’t you can use you’re language specific / write a general function todo so
My Solution to Problem 6:
Code in Python3
n, m = map(int, input().split())
array = [0] * (n+1)
for i in range(m):
a, b, k = map(int, input().split())
array[a] += k
array[b] -= k
# print(array)
array_sum,array_max = 0,0
for i in range(n):
array_sum += array[i]
array_max = max(array_max,array_sum)
print()
print(array_max)
Increase the array[a] by k and decrease array[b] by k for each input a,b,k => time complexity: O(m)
the maximum Iterative sum of resultant array is the output => time complexity: O(n)
Final time complexity: O(m+n) => O(n)
I have to learn maps , I guess any problem can b solved by this.
