Walking on Water

After clearing Maze Palace, use the Boots to walk west on the river until you reach the bridge back to the mainland. You can also walk on water south towards Nabooru Town, bypassing the cave near it.

South of Nabooru, enter a cave. Fight Tektites with Fire if desired. In the next section, defeat an Aruroda by casting Shield, waiting for its eye to open, then crouching and stabbing it (Downthrust can also work). Arurodas drop 150 EXP. At the end of the cave, find a Treasure Bag (500 EXP).

Northeast of the cave, use the Hammer to destroy the boulder blocking the coast.

Follow the coastline east. You can walk on water to avoid enemies. At the eastern end, hug the northern mountain wall to find a hidden area. Cast Jump to ascend the rock wall. Continue right to find another Treasure Bag (500 EXP).

To reach the next palace, head west across the water from Nabooru Town. Walk north onto the sandy terrain two spaces from the water to find a hidden action scene with a Red Magic Jar.

Return to the road and walk east from Nabooru Town onto the sea. Follow the path indicated on the map (or generally: level with the northern coastline protrusion, turn north, go as far as possible, turn east, go to the eastern end). You will find a rocky island in the sea. On this island is Heart Container #3.

Exit the island and return to the overworld. Head east to the Palace on the Sea.