import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Two%20Pointers%20Algorithm%20Technique%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20Pre-requisite%20Concepts%0A%20%20%20%201.%20**Array%20Data%20Structure**%0A%20%20%20%20%20%20%20-%20Understanding%20of%20array%20indexing%0A%20%20%20%20%20%20%20-%20Array%20traversal%0A%20%20%20%20%20%20%20-%20Array%20manipulation%0A%0A%20%20%20%202.%20**String%20Operations**%0A%20%20%20%20%20%20%20-%20Basic%20string%20manipulation%0A%20%20%20%20%20%20%20-%20String%20indexing%0A%0A%20%20%20%203.%20**Sorting**%0A%20%20%20%20%20%20%20-%20Understanding%20of%20sorted%20arrays%0A%20%20%20%20%20%20%20-%20Properties%20of%20sorted%20sequences%0A%0A%20%20%20%204.%20**Time%20Complexity**%0A%20%20%20%20%20%20%20-%20Basic%20understanding%20of%20Big%20O%20notation%0A%20%20%20%20%20%20%20-%20Understanding%20of%20O(n)%20vs%20O(n%C2%B2)%20complexity%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20Detailed%20Notes%0A%0A%20%20%20%20%23%23%23%201.%20Two%20Pointers%20Overview%0A%20%20%20%20-%20Two%20pointers%20is%20a%20general%20algorithmic%20technique%0A%20%20%20%20-%20Sliding%20window%20is%20considered%20a%20subset%20of%20two%20pointer%20problems%0A%20%20%20%20-%20Key%20distinction%3A%0A%20%20%20%20%20%20-%20Two%20Pointers%3A%20Focus%20on%20individual%20elements%20at%20pointer%20positions%0A%20%20%20%20%20%20-%20Sliding%20Window%3A%20Focus%20on%20entire%20window%20between%20pointers%0A%0A%20%20%20%20%23%23%23%202.%20Palindrome%20Check%20Example%0A%20%20%20%20%23%23%23%23%20Approach%0A%20%20%20%20-%20Initialize%20two%20pointers%3A%0A%20%20%20%20%20%20-%20Left%20pointer%20at%20start%0A%20%20%20%20%20%20-%20Right%20pointer%20at%20end%0A%20%20%20%20-%20Compare%20elements%20at%20both%20pointers%0A%20%20%20%20-%20Move%20pointers%20toward%20center%0A%20%20%20%20-%20Stop%20when%20pointers%20cross%0A%0A%20%20%20%20%23%23%23%23%20Time%20Complexity%3A%20O(n)%0A%20%20%20%20%23%23%23%23%20Space%20Complexity%3A%20O(1)%0A%0A%20%20%20%20%23%23%23%203.%20Two%20Sum%20in%20Sorted%20Array%0A%20%20%20%20%23%23%23%23%20Problem%20Description%0A%20%20%20%20-%20Given%3A%20Sorted%20array%0A%20%20%20%20-%20Task%3A%20Find%20two%20numbers%20that%20sum%20to%20target%0A%20%20%20%20-%20Assumption%3A%20Exactly%20one%20solution%20exists%0A%0A%20%20%20%20%23%23%23%23%20Solution%20Approach%0A%20%20%20%201.%20Initialize%20pointers%20at%20array%20edges%0A%20%20%20%202.%20Calculate%20current%20sum%0A%20%20%20%203.%20If%20sum%20%3E%20target%3A%20decrease%20right%20pointer%0A%20%20%20%204.%20If%20sum%20%3C%20target%3A%20increase%20left%20pointer%0A%20%20%20%205.%20If%20sum%20%3D%3D%20target%3A%20found%20solution%0A%0A%20%20%20%20%23%23%23%23%20Key%20Insights%0A%20%20%20%20-%20Utilizes%20sorted%20property%20of%20array%0A%20%20%20%20-%20Eliminates%20impossible%20combinations%0A%20%20%20%20-%20More%20efficient%20than%20brute%20force%20O(n%C2%B2)%0A%20%20%20%20-%20Called%20%22shrinking%20window%22%20pattern%0A%0A%20%20%20%20%23%23%23%23%20Time%20Complexity%3A%20O(n)%0A%20%20%20%20%23%23%23%23%20Space%20Complexity%3A%20O(1)%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20Python%20Examples%0A%0A%20%20%20%20%23%23%23%201.%20Palindrome%20Check%0A%20%20%20%20%60%60%60python%0A%20%20%20%20def%20isPalindrome(s%3A%20str)%20-%3E%20bool%3A%0A%20%20%20%20%20%20%20%20left%2C%20right%20%3D%200%2C%20len(s)%20-%201%0A%0A%20%20%20%20%20%20%20%20while%20left%20%3C%20right%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20s%5Bleft%5D%20!%3D%20s%5Bright%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20left%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20right%20-%3D%201%0A%0A%20%20%20%20%20%20%20%20return%20True%0A%0A%20%20%20%20%23%20Example%20usage%0A%20%20%20%20print(isPalindrome(%22racecar%22))%20%20%23%20True%0A%20%20%20%20print(isPalindrome(%22hello%22))%20%20%20%20%23%20False%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20%23%23%23%202.%20Two%20Sum%20in%20Sorted%20Array%0A%20%20%20%20%60%60%60python%0A%20%20%20%20def%20findTwoSum(nums%3A%20list%5Bint%5D%2C%20target%3A%20int)%20-%3E%20list%5Bint%5D%3A%0A%20%20%20%20%20%20%20%20left%2C%20right%20%3D%200%2C%20len(nums)%20-%201%0A%0A%20%20%20%20%20%20%20%20while%20left%20%3C%20right%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20current_sum%20%3D%20nums%5Bleft%5D%20%2B%20nums%5Bright%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20current_sum%20%3D%3D%20target%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20%5Bleft%2C%20right%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20elif%20current_sum%20%3E%20target%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20right%20-%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20left%20%2B%3D%201%0A%0A%20%20%20%20%20%20%20%20return%20%5B%5D%20%20%23%20No%20solution%20found%0A%0A%20%20%20%20%23%20Example%20usage%0A%20%20%20%20sorted_array%20%3D%20%5B-1%2C%202%2C%203%2C%204%2C%207%2C%208%2C%209%5D%0A%20%20%20%20target%20%3D%207%0A%20%20%20%20print(findTwoSum(sorted_array%2C%20target))%20%20%23%20%5B2%2C%204%5D%20(3%20%2B%204%20%3D%207)%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20%23%23%23%203.%20Generic%20Two%20Pointer%20Template%0A%20%20%20%20%60%60%60python%0A%20%20%20%20def%20twoPointerTemplate(arr%3A%20list)%20-%3E%20None%3A%0A%20%20%20%20%20%20%20%20left%20%3D%200%0A%20%20%20%20%20%20%20%20right%20%3D%20len(arr)%20-%201%0A%0A%20%20%20%20%20%20%20%20while%20left%20%3C%20right%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Process%20elements%20at%20left%20and%20right%20pointers%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Update%20pointers%20based%20on%20condition%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20some_condition%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20left%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20right%20-%3D%201%0A%0A%20%20%20%20%20%20%20%20%23%20Return%20result%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20Key%20Takeaways%0A%20%20%20%201.%20Two%20pointers%20is%20an%20efficient%20technique%20for%20reducing%20time%20complexity%20from%20O(n%C2%B2)%20to%20O(n)%0A%20%20%20%202.%20Particularly%20useful%20for%3A%0A%20%20%20%20%20%20%20-%20Palindrome%20problems%0A%20%20%20%20%20%20%20-%20Finding%20pairs%20in%20sorted%20arrays%0A%20%20%20%20%20%20%20-%20Problems%20requiring%20comparison%20of%20elements%20from%20opposite%20ends%0A%20%20%20%203.%20Often%20eliminates%20need%20for%20extra%20space%2C%20achieving%20O(1)%20space%20complexity%0A%20%20%20%204.%20Most%20effective%20when%20input%20has%20some%20order%20(like%20sorting)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
c4c6e4e110ed7deb8d315b65cff834ee