Data Structures && Algo Problems-1
Question-1(asked in Facebook) Given a sorted array find the square sorted array out of it. Input elements int [] array={-6,-5,-4,1,2,3,4} Output {1 ,4 ,9 ,16 ,25 ,25 ,36 } Answer Now we are stated that we will be given a sorted array as input. Now simply squaring that will change the elements value and that array wont be sorted anymore. So squaring the element gives you 36,25,16,1,4,9,64 so that wont be sorted anymore Now the key is how to perform this kind of problems with optimal solution We will try to solve this problem by O(n) time complexity We will use some extra space complexity. So know the key thing is each one of us knows that we will simply first square the elements and will apply the sort taking the sort function by Arrays.sort(array) but lets make this problem optimal in a single go..!! So firstly will traverse the array taking the left pointer and the right pointer like {-6,-5,-4,1,2,3,4} ^...